Chia dãy

View as PDF

Submit solution


Points: 0.21 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Ioicamp - Marathon 06 - 07
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Dãy số ~M~ phần tử ~B~ được gọi là dãy con của dãy số ~A~ gồm ~N~ phần tử nếu tồn tại một mã chuyển ~C~ gồm ~M~ phần tử thoả mãn ~B_i = A_{C_{i}}~ với mọi ~i = 1...M~ và ~1 \le C_1 < C_2 < ... < C_m \le N~.

Một cách chia dãy ~A~ thành các dãy con "được chấp nhận" nếu các dãy con này là các dãy không giảm và mỗi phần tử của dãy ~A~ thuộc đúng một dãy con.

Yêu cầu: Bạn hãy chia dãy con ban đầu thành ít dãy con nhất mà vẫn "được chấp nhận".

Input

Dòng đầu tiên ghi số ~N~ là số phần tử của dãy ~A~ (~N \le 10^{5}~).

~N~ dòng tiếp theo ghi ~N~ số tự nhiên là các phần tử của dãy ~A~ (~A_{i} \le 10^{9}~).

Output

Ghi một số duy nhất là số lượng dãy con ít nhất thỏa mãn.

Sample Input

4
1
5
4
6

Sample Output

2

Comments

Please read the guidelines before commenting.



  • -6
    vndkhoi  commented on June 14, 2023, 3:45 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.