Problem Description

Xiaoxue is very interested in bicycle races, especially the Lake Ring Bicycle Race. The annual Lake Ring Bicycle Race requires participants to compete for several consecutive days, and the champion is determined by the cumulative scores. This year, there are $N$ participants. Each day's race determines the ranking for that day, with the first-place participant earning $N$ points, the second-place earning $N-1$ points, the third-place earning $N-2$ points, and so on, with the last-place earning $1$ point. It is guaranteed that no two participants will have the same rank.

In the previous days of competition, the $N$ participants have already accumulated some scores. Now, the final day of the race is about to begin. Xiaoxue wants to know how many participants still have a chance to win the final championship, i.e., how many participants can potentially achieve the highest cumulative score through the final day's race.

Input Format

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

The next $N$ lines each contain an integer $B_i$, representing the cumulative score already obtained by the $i$-th participant, with $0 \le B_i \le 2 \times 10^6$.

Output Format

Output a single line containing a single integer, representing the number of participants who still have a chance to win the final championship.

Sample Input and Output

Sample Input #1

3
8
10
9

Sample Output #1

3

Sample Input #2

5
15
14
15
12
14

Sample Output #2

4

Notes/Hints

Data Range and Constraints

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

见题面 Input 部分

见题面 Output 部分