Wrestling Competition

Time limit1sMemory limit512 MB

Summary

Given strengths and a threshold K, count players who could be the last survivor when random pairings are played and a match is decided by strength unless the gap is at most K.

Level: Medium6 of 10
Topics: Sorting, Greedy, Math, Implementation
Solved: No attempts yet

Problem

A wrestling competition will be held tomorrow. A total of $n$ players take part in it. The $i$ -th player's strength is $a_i$ .

If the $i$ -th player and the $j$ -th player have a match, the result depends solely on $|a_i - a_j|$ . If $|a_i - a_j| > K$ , the player with the higher strength wins. Otherwise, each player has a chance to win.

The competition rules are a little strange. For each match, the referee picks two players uniformly at random from all remaining players and holds a match between them. The loser is eliminated. After $n - 1$ matches, the last remaining player is the winner.

Given $n$ , $K$ , and the array $a$ , find how many players have a chance to win the competition.

Input

The first line contains two integers $n$ and $K$ ( $1 \leq n \leq 10^5$ , $0 \leq K < 10^9$ ).

The second line contains $n$ integers $a_i$ ( $1 \leq a_i \leq 10^9$ ).

Output

Print a single line with a single integer: the number of players which have a chance to win the competition.

Examples2

Example 1
Input
```
5 3
1 5 9 6 3
```
Expected output
```
5
```
Example 2
Input
```
5 2
1 5 9 6 3
```
Expected output
```
1
```