Description

There are $N$ players participating in a contest. In each round, the player in 1st place gets $N$ points, the player in 2nd place gets $N - 1$ points, and so on, with the last player getting $1$ point.

Now the $i$-th player initially has $B_i$ points. Determine how many players, after one round, have a chance for their score to become the highest among all players.

Input Format

The input has $N + 1$ lines.

The first line contains a positive integer $N$, the total number of players.

The next $N$ lines each contain an integer $B_i$, the initial score of the $i$-th player.

Output Format

Output one line with an integer, the number of players whose score has a chance to become the highest among all players.

3
8
10
9

3

5
15
14
15
12
14

4

Hint

Constraints

For $100\%$ of the testdata, $3 \le N \le 3 \times 10^5$, $1 \le B_i \le 2 \cdot 10^6$.

Notes

The score setting of this problem follows the original COCI problem, with a full score of $80$.

Translated from COCI2012-2013 CONTEST #1 T2 F7.

Translated by ChatGPT 5