Mô tả và yêu cầu

Chia dãy

H iện tại , bài tập này đã có trên onl i ne j udge chính th ức của V N OI, b ạn có th ể truy cập ở đây:
https://oj .vnoi .i nfo/probl em/qbdi vseq

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 ≤ C [1] < C [2] < ... < C [m] ≤
N .

Mộ t cách chi a 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 chi a dãy con ban đ ầ u thành ít dãy con nh ấ t mà vẫ n " đ ượ c ch ấp nh ận" .

In p u t

D òng đ ầ u ti ên ghi số N l à số ph ầ n tử của dãy A . ( N ≤ 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 ≤ 10 9 )

Ou tp u t

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

E x a mp le

I nput:
4
1
5
4
6

Dữ liệu ra

2