← 返回题目列表

AtCoder · past202112_l

L. 诚实的学生

中文机器翻译题面 查看原题

分数: 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