描述

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

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

格式

输入格式

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

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

输出格式

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

样例1

样例输入1

3
8
10
9

样例输出1

3

样例2

样例输入2

5
15
14
15
12
14

样例输出2

4

限制

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

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

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