Preparing NOJ

自行车比赛

0ms 0K

Description:

小雪非常关注自行车比赛,尤其是环滨湖自行车赛。一年一度的环滨湖自行车赛,需要选手们连续比赛数日,最终按照累计得分决出冠军。今年一共有N位参赛选手。每一天的比赛总会决出当日的排名,第一名的选手会获得N点得分,第二名会获得N-1点得分,第三名会获得N-2点得分,依次类推,最后一名会获得1点得分。保证没有选手会排名相同。

在之前的数日较量中,N位选手已经分别累计了一些分数。现在即将开始的是最后一天的比赛。小雪希望知道有多少位选手还有可能获得最终的冠军,也就是说还有多少选手有可能通过最后一天的比赛获得累计总分第一名。

Input:

第一行输入一个整数N,表示参赛选手总数,保证3<=N<=300000。

之后N行,其中第i行输入一个整数B[i]表示第i位选手已经获得的累计分数,满足0<=B[i]<=2000000。

Output:

输出只有一行,只输出一个整数,表示有多少位选手有可能获得最终的冠军。

Sample Input:

3
8
10
9

Sample Output:

3

Sample Input:

5
15
14
15
12
14

Sample Output:

4

Note:

对于20%的数据,3<=N<=600。

对于50%的数据,3<=N<=10000。

对于100%的数据,3<=N<=300000且0<=B[i]<=2000000。

Info

Vijos

Provider Vijos

Origin P1988 自行车比赛

Code VIJ1988

Tags

Submitted 1

Passed 1

AC Rate 100%

Date 03/10/2019 19:13:39

Related

Nothing Yet