Tóm tắt: Cho dãy số nguyên \(A\) độ dài \(N\).

Yêu cầu: Hãy tìm cách xóa đi ít phần tử nhất sao cho phần còn lại là một dãy tăng.

Input

Đọc từ file văn bản TANGQUA.INP:

• Dòng 1 chứa \(N\), \((1 \leq N \leq 10^5)\)
• Dòng 2 chứa các số nguyên của mảng \(A\), \((1 \leq A_i \leq 10^9)\).

Output

Ghi ra file văn bản TANGQUA.OUT một số nguyên duy nhất là kết quả bài toán.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 100\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 5 \times 10^3\).
• Subtask \(2\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

5
1 3 3 2 8

2