Description

$n$ students (numbered from $1$ to $n$) arrive at the gym at the same time to register and check in, and to receive their admission tickets and contest materials. To keep the registration orderly, these $n$ students must line up in a straight line from front to back in increasing order of their numbers (the student with number $1$ stands at the very front). However, each student dislikes crowding: for the $i$-th student, if there is another student whose distance to him/her is less than $a_i$, a conflict occurs. Xiao Keke wants to know, under the condition that no conflicts occur, what is the minimum possible length of the queue formed by these $n$ students.

Input Format

The first line contains an integer $n$, the number of students.

The second line contains $n$ integers. The $i$-th integer $a_i$ denotes the distance that the $i$-th student must keep from other students.

Output Format

Output one line with a single integer, the minimum possible length of the queue formed by these $n$ students.

Note: The $n$ students must line up from front to back in the order $1$ to $n$.

3
3 1 2

5

Hint

For $20\%$ of the testdata: $1\le n\le 20$.

For $70\%$ of the testdata: $1\le n\le 10^4$.

For $100\%$ of the testdata: $1\le n\le 10^5$，$1\le a_i\le 10^5$.

Translated by ChatGPT 5