Chia dãy
Xem dạng PDF
Gửi bài giải
Điểm:
0,11 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
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
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.