Đề bài

Bố Tí là một người rất giàu có. Ông sở hữu nhiều đất đai và các món đồ quý hiếm. Đặc biệt, ông có một bộ sưu tập gồm \(n\) món đồ cổ, mỗi món được đánh số từ \(1\) đến \(n\) và có giá trị nhất định.

Sau khi được các chuyên gia định giá, giá trị của món đồ cổ thứ \(i\) là \(a_i\).
Tí là con trai duy nhất, nên bố quyết định tặng cho Tí một số món trong bộ sưu tập. Tuy nhiên, có một yêu cầu:
- Các món đồ mà Tí chọn phải có số thứ tự tăng dần và giá trị tăng dần (mỗi món sau phải có giá trị lớn hơn hoặc bằng món trước).

Yêu cầu: Hãy giúp Tí chọn nhiều món đồ nhất có thể để số món đồ không được chọn là ít nhất.

Dữ liệu vào

• Tệp TANGQUA.INP gồm:
• Dòng đầu tiên chứa một số nguyên dương \(n\) (\(1 \leq n \leq 10^5\)) là số lượng món đồ cổ.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \leq a_i \leq 10^9\)) là giá trị của từng món đồ.

Dữ liệu ra

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

Ràng buộc

• 40% số test có \(n \leq 25\).
• 30% số test có \(25 < n \leq 2000\).
• 30% số test không có ràng buộc gì thêm.

Sample Input 1

5
1 3 3 2 8

Sample Output 1

2

Giải thích

• Tí có thể chọn các món đồ ở vị trí (1, 3, 5) với giá trị tương ứng (1, 3, 8).
• Số món đồ không được chọn là 5 - 3 = 2.