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:1s
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
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?
2014-09-18 16:42:57 Trương Quang Trí
sao chạy bị lỗi NZEC là sao vậy? Hình như là lỗi chạy k đc test lớn, ai có test lớn nào cho mình thử với !!!
2014-08-03 02:47:49 ■■‡[ND] Bee Sociu■■‡
sao ma bi loi SIGSGVE the nay ! Do phuc tap nhu bai LIS thoi mak ?! huhu :(
2013-08-09 08:43:36 a;slkfjasl;fkj
nghĩ kĩ thì thấy rất hay ^^ :D

Last edit: 2013-08-10 04:47:45
2013-05-09 09:12:55 Bitagi97
Đề nghĩa là răng ta, khó hiểu
2012-12-22 08:24:54 noone_else
f
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.