Bố Tí là một người rất giàu có, ông có rất nhiều đất đai và các món đồ quý hiếm. Đặc biệt ông có bộ sưu tập gồm 𝑛 món đồ cổ được đánh số thứ tự từ 1 đến 𝑛 có giá trị cao. Ông đã nhờ các chuyên gia về đồ cổ định giá cho từng món đồ cổ của mình. Sau khi định giá các chuyên gia đã đưa ra giá trị của món đồ cổ thứ 𝑖 là 𝑎𝑖(∀𝑖 = 1..𝑛). Tí là đứa con duy nhất nên ông đã quyết định tặng cho Tí một số món từ bộ sưu tập đồ cổ của mình để làm vốn riêng. Ông cho Tí được tự ý lựa chọn các món đồ tuy nhiên có một yêu cầu cho Tí là các món chọn sau phải có số thứ tự và giá trị cao hơn món chọn trước đó.

Yêu cầu:

Hãy giúp Tí tính xem phải chọn những món đồ trong bộ sưu tập đồ cổ như thế nào để số món đồ không được chọn là ít nhất.

Dữ liệu vào:

Đọc từ tệp văn bản TANGQUA.INP

• Dòng thứ nhất chứa số nguyên dương ~𝑛~(~n ≤ 10^5~) là số lượng các món đồ cổ.
• Dòng thứ hai ghi 𝑛 số nguyên ~𝑎_1,𝑎_2,…,a_𝑛~(~1 ≤ 𝑎_𝑖 ≤ 10^9~) là giá trị của từng món đồ.

Dữ liệu ra:

Ghi ra tệp văn bản TANGQUA.OUT một số nguyên duy nhất là số món đồ cổ Tí không chọn.

Ví dụ:

TANGQUA.INP

5 
1 3 3 2 8

TANGQUA.OUT

2

Giải thích

Tí chọn được 3 món đồ trong 5 món ở các vị trí lần lượt là (1, 3, 5)

Ràng buộc:

• Có 40% số test đầu với 𝑛 ≤ 25;
• Có 30% số test tiếp theo với 25 < 𝑛 ≤ 2000;
• Có 30% số test còn lại không có ràng buộc gì thêm.