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

Cho một dãy số nguyên gồm N phần tử a1, a2, ..., an.

Biết rằng dãy con tăng đơn điệu là 1 dãy ai1, ai2, ..., aik thỏa mãn i1 < i2 < ... < ik và ai1 < ai2 < ... < aik. Hãy cho biết số dãy con tăng đơn điệu ít nhất có dãy số gồm n phần tử trên.

VD: dãy (6, 7, 4, 2, 5) thì sẽ có ít nhất 3 dãy con tăng đơn điệu là (6, 7) và (4, 5) và (2).

Dữ liệu vào

Dữ liệu vào: SEQ8.inp

Dòng 1 gồm 1 số nguyên là số N.

Dòng thứ 2 ghi N số nguyên a1, a2, ..., an (1 ≤ ai ≤ 10^9).

Dữ liệu ra

Kết quả: SEQ8.out

In ra kết quả là số dãy con tăng đơn điệu ít nhất.

Giới hạn và chấm điểm

Sub1: n < 5000.
Sub2: n <= 500000.

Ví dụ

7
8 -10 6 -5 9 1 -3

4

Các dãy con tăng là (8); (-10, 6, 9); (-5, 1) và (-3).