分数: 6 点
问题陈述
N 学生参加了一次测试,每个人的分数都在 0 和 P (含)。所有学生均获得不同的分数,并按分数降序排列。
高桥询问每个学生的分数,学生排名 i-th 告诉他他们得分了 A_i.
然而,有些学生可能撒了谎。
找出说谎的学生的最少可能数量。
约束
- 2 \leq N \leq 2\times 10^5
- N-1 \leq P \leq 10^9
- 0 \leq A_i \leq P
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N P A_1 A_2 \ldots A_N
输出
打印出说谎的学生的最少可能数量。
示例输入 1
5 10 7 5 10 3 2
示例输出 1
1
如果只是学生排名 3-rd 在真实分数为 4,学生的分数和排名将保持一致。
如果所有学生都说了实话,则该学生排名 3-rd 的得分会高于排名的学生 2-nd,这不可能发生。
因此,说谎的学生的最小可能数量是 1.
示例输入 2
5 10 9 8 7 7 5
示例输出 2
1
请注意,学生的真实分数是不同的。
示例输入 3
11 1000000000 0 1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000
示例输出 3
10