You are given an integer array arr of size n, representing the points on the X-axis on the Cartesian coordinate plane.

You are given an integer array arr of size n, representing the points on the X-axis on the Cartesian coordinate plane.

In one operation, you can select any two points xi and xj (i ≠ j) from the array such that the distance between the two points is at least K and remove the two points from the array.

Hackathon

Your task is to calculate the maximum number of above described operations that you can perform.

Example:

n =6

arr = [1, 2, 3, 4, 5, 6] K =4

There are n = 6 points. Considering 0-based indexing, there are only two pairs of points that have a difference of 4 or more which you can remove one by one: (1, 5) and (2, 6), corresponding to the indices (0, 4) and (1, 5).

Operation 1: arr: [ 1, 2, 3, 4, 5, 6 ] -> [ _, 2, 3, 4, _, 6 ] 

Operation 2: arr: [ _, 2, 3, 4, _, 6] -> : [ _, _, 3, 4, _ , _ ]

After performing these two operations you cannot remove any pair of points from the array since the distance between any pair of points left will be less than K(=4). Hence the answer is 2.

Constraints:

● 1<n<105

● 0<K<109

● 1 < arr[i]< 109

The first line contains an integer, n, denoting the number of points on the X-axis. Each line i of the n subsequent lines (where 1 ≤ i < n) contains an integer arr[i],

representing the ith point on the X-axis.

The last line of the input contains the integer K, the minimum permissible distance between two points.

Output Format :

Your task is to print the maximum number of above described operations that you can perform.

Sample Testcase #0

Testcase Input

4 
1 
1 
1 
1 
1

Testcase Output :

0

Explanation :

n =4

arr = [1, 1, 1, 1]

K =1

There are no pair of points such that the distance between them is at least 1. Hence you cannot perform any operation. Hence the answer is 0.

Sample Testcase #1

Testcase Input :

6 
3 
4 
5 
2 
1
1 
3
  

Testcase Output :
0

Explanation :

n =6 

arr = [3, 4, 5, 2, 1, 1] 

K =3 

 There are n = 6 points. Considering 0-based indexing, there are only two pairs of points that have a difference of 4 or more which you can remove one by one: (5, 2) and (4, 1), corresponding to the indices (2, 3) and (1, 4). 

Operation 1: arr: [3, 4, 5, 2, 1, 1] -> [3, 4, _, _, 1, 1] 

Operation 2: arr: [3, 4, _, _, 1, 1] -> : [3, _, _, _, _, 1] 

 After performing these two operations you cannot remove any pair of points from the array since the distance between any pair of points left will be less than K(=3). Hence the answer is 2.

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, K;
    cin >> n;

    vector arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    cin >> K;

    sort(arr.begin(), arr.end());

    int operations = 0;
    int left = 0, right = n - 1;

    while (left < right) {
        if (arr[right] - arr[left] >= K) {
            ++operations;
            ++left;
            --right;
        } else {
            --right;
        }
    }

    cout << operations << endl;

    return 0;
}