/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
問題文
N 人の生徒がテストを受け、それぞれ 0 以上 P 以下の整数の得点を得ました。各生徒の得た得点は相異なり、得点の高い順に順位付けされています。
高橋君がそれぞれ生徒に得点を聞いたところ、i 位の生徒は自分の得点を 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 位の生徒だけが嘘をついており、3 位の生徒の本当の得点が 4 点だった場合は得点と順位が符合します。
生徒が全員本当のことを言っていたとすると、3 位の生徒の得点が 2 位の生徒の得点より高くなってしまうため、そのようなことはありません。
よって嘘を付いている生徒の人数として考えられる最小値は 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
Score : 6 points
Problem Statement
N students took a test, each getting a score of a positive integer between 0 and P (inclusive). All students got different scores, and they were ranked in descending order of score.
Takahashi asked each student their score, and the student ranked i-th told him they scored A_i.
However, some of the students might have told a lie.
Find the minimum possible number of students who told a lie.
Constraints
- 2 \leq N \leq 2\times 10^5
- N-1 \leq P \leq 10^9
- 0 \leq A_i \leq P
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N P A_1 A_2 \ldots A_N
Output
Print the minimum possible number of students who told a lie.
Sample Input 1
5 10 7 5 10 3 2
Sample Output 1
1
If just the student ranked 3-rd told a lie when the true score was 4, the students' scores and ranks would be consistent.
If all students had told the truth, the student ranked 3-rd would have scored higher than the student ranked 2-nd, which could not happen.
Therefore, the minimum possible number of students who told a lie is 1.
Sample Input 2
5 10 9 8 7 7 5
Sample Output 2
1
Note that the true scores of the students are distinct.
Sample Input 3
11 1000000000 0 1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000
Sample Output 3
10