Migrated from Lutece 2573 辉夜大小姐想和我参加 ICPC

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

四宫辉夜最近对算法竞赛很感兴趣，她邀请白银御行一起参加暑假前集训，以进入秀知院校队。这个世界的神——赤坂向你透露：现在白银的 Codeforces rating 为 $a_0$，接下来有 $n$ 场 Codeforces 比赛，参加第 $i$ 场比赛会使白银的 rating 变成 $a_i$。

为了避免让辉夜发现自己有不擅长的东西，白银不希望自己的 rating 在某场比赛后下降，所以他可以跳过一些比赛。但他又希望能参加尽量多的场次，这样他才能真正提升自己的算法水平。白银忙着去写 DP 专题了，他请你帮他预计最多能参加多少场比赛。

Input

第一行输入一个整数 $n\ (0\le n\le 10^6)$，表示接下来有 $n$ 场 Codeforces 比赛。

第二行输入 $n+1$ 个整数 $a_0,a_1,\ldots ,a_n\ (0\le a_i\le 10^9)$，$a_0$ 表示初始 rating，$a_i\ (i>0)$ 表示第 $i$ 场比赛后白银的 rating。

Output

输出一个整数 $m$，表示白银最多能参加 $m$ 场比赛。

Samples

6
1500 1502 1501 1509 1507 1508 1510

4

Note

样例中，白银最多能参加 $4$ 场比赛，其中一种方案为：参加第 $1,4,5,6$ 场比赛，这样他实际获得的 rating 序列为 $1500,1502,1507,1508,1510$，单调不降。

Resources

2021 UESTC ICPC Training for Dynamic Programming