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ó 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ó.

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:

• 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 ≤ 10^6\).

Kết quả:

• 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:

• 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\)

Sample Input

6
3 4 1 6 7 7

Sample Output

1

Sample Input

5
1 2 3 4 5

Sample Output

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.