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ó dạng một chuỗi các khối, mỗi khối bắt đầu bằng độ dài của nó, tức là trước tiên là độ dài của khối và sau đó là các phần tử của nó. Dãy rỗng cũng được coi là dãy đẹp vì độ dài của dãy là 0 và không tồn tại phần tử nào trong dãy.

Ví dụ:

• Dãy đẹp là [3, 3, 4, 5, 2, 6, 1] vì có thể tách thành hai khối [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 khối [1, 8] và [4, 3, 2, 7, 2]

Trong khi các dãy [1, 4, 3], [3, 2, 1], [2], … thì không phải dãy đẹp.

Yêu cầu: Một thao tác xóa được tính là bạn có thể xóa bất kỳ phần tử nào khỏi dãy số. Cần tối thiểu bao nhiêu thao tác xóa để dãy đã cho trở thành dãy đẹp?

Dữ liệu vào:

• Dòng đầu tiên là số nguyên dương n.
• 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 \leq 10^6\)

Dữ liệu ra:

Ghi ra 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).

Ràng buộc:

• Có 30% số test của bài có \(1 < n \leq 100\)
• Có 30% số test của bài có \(100 < n \leq 1000\)
• Có 40% số test còn lại của bài có \(1000 < n \leq 10^5\)

Input 1:

6
3 4 1 6 7 7

Ouput 1:

1

Input 2:

5
1 2 3 4 5

Ouput 2:

2

Giải thích:

• Với ví dụ 1, chúng ta sẽ lựa 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.
• Với 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.