You are given a set of points x1x1, x2x2, ..., xnxn on the number line.
Two points ii and jj can be matched with each other if the following conditions hold:
- neither ii nor jj is matched with any other point;
- |xi−xj|≥z|xi−xj|≥z.
What is the maximum number of pairs of points you can match with each other?
Input
The first line contains two integers nn and zz (2≤n≤2⋅1052≤n≤2⋅105, 1≤z≤1091≤z≤109) — the number of points and the constraint on the distance between matched points, respectively.
The second line contains nn integers x1x1, x2x2, ..., xnxn (1≤xi≤1091≤xi≤109).
Output
Print one integer — the maximum number of pairs of points you can match with each other.
Examples
Input4 2 1 3 3 7
Output
2
Input
5 5 10 9 5 8 7
Output
1
Note
In the first example, you may match point 11 with point 22 (|3−1|≥2|3−1|≥2), and point 33with point 44 (|7−3|≥2|7−3|≥2).
In the second example, you may match point 11 with point 33 (|5−10|≥5|5−10|≥5).
#include <iostream> #include <algorithm> #include <cstdio> #include <string> #include <cstring> #include <cstdlib> #include <map> #include <vector> #include <set> #include <queue> #include <stack> #include <cmath> // #define lson rt<<1, l, m #define rson rt<<1|1, m+1, r // #define fi first #define se second #define pb push_back #define pq priority_queue<int> #define ok return 0; #define os(str) cout<<string(str)<<endl; #define gcd __gcd #define mem(s,t) memset(s,t,sizeof(s)) #define debug(a,n) for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; #define debug1(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" "; cout<<endl; #define debug02(a,n,m) for(int i=0;i<n;i++) {for(int j=0;j<m;j++) cout<<a[i][j]<<" "; cout<<endl; } #define read11(a,k) for (int i = 1; i <= (int)(k); i++) {cin>>a[i];} #define read02(a,n,m) for(int i=0;i<n;i++) {for(int j=0;j<m;j++) cin>>a[i][j] ; } #define TLE std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout.precision(10); using namespace std; inline void NO() { cout<<"NO"<<endl; } inline void YES() { cout<<"YES"<<endl; } const int mxn = 2e5+10; #define oi(x) cout<<x<<endl; #define rep(k) for (int i=0;i<n;i++) #define rep1(j,k) for (int i=j;i<=k; i++) #define per(j,k) for (int i=j;i>=k; i--) //#define per(k) for (int i=k-1;i>=0;i--) #define lli long long string str,ch; lli a[mxn],vis[mxn]; int n,k,ans; int judge(int mid) { for(int i=n-mid ,j=0; i<n;i++) { if(a[i]-a[j]<k) { return 0; } else j++; } ans = mid; return 1; } int main() { while(cin>>n>>k) { ans = 0; for(int i=0;i<n;i++) cin>>a[i]; sort(a,a+n); int l = 0 ,r = n/2 , mid; while(l<=r) { mid = l + ( (r-l)>>1 ); //cout<<" +++ "<<ans<<endl; if(judge(mid)) l = mid +1 ; else r = mid - 1; } cout<<ans<<endl; } ok; }