Cycling Championship Final Day Prospects

In the annual cycle race around Binhu, there are N participants. Over the previous days, each participant has accumulated some points. On the final day, the race awards points based on the finishing order. The first placed rider receives N points, the second N-1 points, the third N-2 points, and so on, with the last rider receiving 1 point. All rankings are distinct.

Let the initial scores be \(s_1, s_2, \ldots, s_N\). On the final day, if participant \(i\) finishes first, his final score becomes \(s_i+N\). Meanwhile, the points for the other participants are assigned as a permutation of \(\{1,2,\ldots,N-1\}\>.

A participant \(i\) can become the overall champion (i.e. have the strictly highest total score) if there exists a valid assignment of the remaining points to the other participants such that for every other participant \(j\) the final score \(s_j+\text{assigned}_j\) is strictly less than \(s_i+N\). It can be shown that the optimal way to minimize the maximum of the other participants' final scores is to assign the smallest available finishing points to the participants with the highest initial scores. In other words, if we sort the other participants in non‐increasing order by score and assign them finishing points \(1, 2, \ldots, N-1\) in that order, then participant \(i\) can be champion if and only if

[ s_i+N > \max_{0 \le k < N-1} \Big(\text{other}_{k}+ (k+1)\Big). ]

Your task is to compute how many participants still have the possibility of becoming the overall champion.

inputFormat

The first line of input contains an integer N (the number of participants). The second line contains N space-separated integers representing the current scores \(s_1, s_2, \ldots, s_N\) for each participant.

outputFormat

Output a single integer representing the number of participants who can possibly become the overall champion.

sample

3
2 2 2

3