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:
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
ai giari thisch ddeef hooj voiws duwojdc khoong aj
This comment is hidden due to too much negative feedback. Show it anyway.