Chia dãy
Xem dạng PDF
Gửi bài giải
Điểm:
0,21 (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
ai giari thisch ddeef hooj voiws duwojdc khoong aj
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.