/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 425 点
問題文
長さ N の整数列 A=(A_1,A_2,\dots,A_N) と非負整数 D が与えられます。 A の要素をいくつか削除して、以下の条件を満たす数列 B を得たいです。
- すべての i,j \; (1 \leq i < j \leq |B|) について、|B_i-B_j| \neq D
最小でいくつの要素を削除すればよいか求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq D \leq 10^6
- 0 \leq A_i \leq 10^6
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N D A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
5 2 3 1 4 1 5
出力例 1
1
A_1=3 を削除して B=(1,4,1,5) とすることで、すべての i<j について |B_i-B_j|\neq 2 となります。
入力例 2
4 3 1 6 1 8
出力例 2
0
A がすでに条件を満たしていることもあります。
入力例 3
10 3 1 6 2 10 2 3 2 10 6 4
出力例 3
2
Score : 425 points
Problem Statement
You are given a length-N integer sequence A=(A_1,A_2,\dots,A_N) and a non-negative integer D. We wish to delete as few elements as possible from A to obtain a sequence B that satisfies the following condition:
- |B_i - B_j|\neq D for all i,j \; (1 \leq i < j \leq |B|).
Find the minimum number of deletions required.
Constraints
- 1 \le N \le 2\times 10^5
- 0 \le D \le 10^6
- 0 \le A_i \le 10^6
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N D A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
5 2 3 1 4 1 5
Sample Output 1
1
Deleting A_1=3 yields B=(1,4,1,5), which satisfies |B_i - B_j|\neq 2 for all i<j.
Sample Input 2
4 3 1 6 1 8
Sample Output 2
0
The sequence A may already satisfy the condition.
Sample Input 3
10 3 1 6 2 10 2 3 2 10 6 4
Sample Output 3
2