Description

Xiaoxue is very interested in bicycle races, especially the Tour of Binhu Lake. The annual Tour of Binhu Lake requires riders to compete for several consecutive days, and the champion is decided by total accumulated points. This year there are $N$ contestants. Each day’s race produces a ranking: the first-place finisher earns $N$ points, the second-place finisher earns $N-1$ points, the third-place finisher earns $N-2$ points, and so on, with the last-place finisher earning $1$ point. It is guaranteed that no two contestants share the same rank on a given day.

Over the previous days, the $N$ contestants have already accumulated some points. The final day is about to begin. Xiaoxue wants to know how many contestants still have a chance to become the overall champion — that is, how many contestants can possibly finish with the highest total after the last day’s race.

Input Format

The first line contains an integer $N$, the total number of contestants, with $3\le N\le 3\times 10^5$.

Then follow $N$ lines. The $i$-th line contains an integer $B_i$, the accumulated points already earned by contestant $i$, with $0\le B_i\le 2\times 10^6$.

Output Format

Output a single line containing one integer: the number of contestants who can still become the final champion.

3
8
10
9

3

5
15
14
15
12
14

4

Hint

Constraints and Conventions

• For $20\%$ of the testdata, $3\le N\le 600$.
• For $50\%$ of the testdata, $3\le N\le 1\times 10^4$.
• For $100\%$ of the testdata, $3\le N\le 3\times 10^5$ and $0\le B_i\le 2\times 10^6$.

Translated by ChatGPT 5