Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QBDIVSEQ - Chia dãy

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 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 ≤ 105 )

N dòng tiếp theo ghi N số tự nhiên là các phần tử của dãy A. ( Ai ≤ 109 )

Output

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

Example

Input:
4
1
5
4
6

Output:
2


Được gửi lên bởi:special_one
Ngày:2008-12-10
Thời gian chạy:0.117s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Ioicamp - Marathon 06 - 07

hide comments
2017-07-28 05:48:56
Code AC: http://shink.in/xo0sj
2017-07-08 10:26:41
chặt nhị phân mà còn quá thời gian huh =='
2017-02-12 15:25:49
why đs= độ dài dãy con giảm zậy mn
2016-10-04 11:25:22
/ff enter
2016-05-14 12:42:03
Nếu hiểu rõ mở rộng của dãy con tăng thì bài này đơn giản, bài hay!
2016-04-16 08:30:21


Last edit: 2016-04-16 08:48:54
2016-01-30 08:54:35
THAM KHẢO: http://codevnspoj.blogspot.com/
2015-11-17 10:47:16
bai qua hay
2014-11-27 09:37:36 Dương Bảo
bài hay thật
2014-11-06 14:44:42 Nguyễn Duy Long
Có phải số lượng dãy con ít nhất chính là độ dài lớn nhất của dãy con giảm?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.