Bạn An là một học sinh rất yêu thích môn toán, đặc biệt là các bài toán liên quan đến dãy số. Gần đây, An phát hiện ra một quy luật khá thú vị đối với dãy số và An gọi đó là “dãy số đẹp”. Theo quy luật của An thì với dãy số nguyên ~ a ~ gồm ~ n ~ phần tử, dãy ~ a ~ được gọi là “đẹp” nếu nó có thể được chia thành nhiều đoạn liên tiếp các phần tử (cũng có thể là 1 đoạn), mỗi đoạn gồm phần tử đầu tiên có giá trị ~X~ thì tiếp theo sau là ~X~ phần tử.

Ví dụ:

• Dãy đẹp là [3, 3, 4, 5, 2, 6, 1] vì có thể tách thành hai đoạn [3, 3, 4, 5] và [2, 6, 1]
• Dãy đẹp là [1, 8, 4, 3, 2, 7, 2] vì có thể tách thành hai đoạn [1, 8] và [4, 3, 2, 7, 2]
• Còn các dãy số sau [1, 4, 3], [3, 2, 1], [2] không phải dãy số đẹp.

Yêu cầu: Thực hiện ít nhất số lần xóa các phần tử bất kỳ của dãy số để tạo ra dãy số đẹp.

Dữ liệu vào:

• Dòng 1: Chứa số nguyên dương ~ n ~ (1 < n ≤ 10^5).
• Dòng thứ hai gồm ~ n ~ số nguyên trong dãy ~ a ~ mỗi số cách nhau bởi một khoảng trắng và ~ 1 ≤ a_i ≤ 10^6~, với ~i=1..n ~.

Kết quả:

• Một dòng ghi một số nguyên duy nhất là số lần xóa tối thiểu để được dãy đẹp. Trường hợp dãy đầu vào đã là dãy đẹp sẵn thì in ra kết quả là 0 (tức 0 lần xóa). Dữ liệu đảm bảo luôn có cách xóa để dãy còn lại là dãy đẹp.

Ví dụ:

Input 1:

6
3 4 1 6 7 7 

Output 1:

1 

Input 2:

5
1 2 3 4 5 

Output 2:

2 

Giải thích ví dụ 1:

• Chọn xóa số 3 (tức phần tử ~ a[1] ~) để được dãy đẹp là [4, 1, 6, 7, 7]. Do đó đáp án là 1 lần xóa.

Giải thích ví dụ 2:

• Chúng ta sẽ lựa chọn xóa số 1 và 5 (tức phần tử ~ a[1] ~ và ~ a[5] ~) để được dãy đẹp là [2, 3, 4]. Do đó, đáp án là 2 lần xóa. Hoặc cũng có thể xóa số 1 và 3 hoặc 1 và 4.

Ràng buộc:

• 40% số điểm của bài có ~ 1<n≤100 ~
• 60% số điểm còn lại của bài có ~ 1<n≤10^5 ~