Potential Champion

There are \(N\) contestants in a competition. In each round, the contestant finishing in 1st place gets \(N\) points, the 2nd place gets \(N-1\) points, and so on, until the last place gets 1 point. Initially, the \(i\)th contestant has \(B_i\) points. In one round, the round points will be distributed in some permutation among the contestants. Determine how many contestants have a chance such that if they receive the maximum round score (i.e. \(N\) points) and the remaining contestants receive points in an optimally minimal way, their final total score, \(B_i+N\), can be strictly higher than every other contestant’s final total.

Formally, when contestant \(i\) is considered, we are allowed to assign the round scores, which are the set \(\{1, 2, \ldots, N\}\), with contestant \(i\) fixed to receive \(N\) points. For the remaining contestants, an assignment \(f:\{j\neq i\}\to\{1,2,\ldots,N-1\}\) (a permutation) is chosen in order to minimize their maximum final score. One optimal strategy is to sort the remaining contestants by their initial scores in non‐increasing order and assign the smallest possible round score to the highest scoring contestant, the second smallest to the second highest, and so forth. That is, if after removing contestant \(i\) the sorted order is \(\{B_{(1)}, B_{(2)},\ldots, B_{(N-1)}\}\ (B_{(1)} \ge B_{(2)} \ge \cdots \ge B_{(N-1)})\), they are assigned points \(1, 2,\ldots, N-1\) respectively. Contestant \(i\) can become the champion if and only if \[ B_i+N > \max_{1\le p\le N-1} \Bigl(B_{(p)}+p\Bigr). \] Your task is to compute the number of potential champions.

inputFormat

The first line contains an integer \(N\) (the number of contestants). The second line contains \(N\) space‐separated integers \(B_1, B_2, \ldots, B_N\) representing the initial scores of the contestants.

outputFormat

Output a single integer representing the number of contestants who have a chance to become the champion after one round.

sample

3
2 2 2

3