C Match Points（Educational Codeforces Round 64 (Rated for Div. 2)）的解题思路是什么？

本文共计1156个文字，预计阅读时间需要5分钟。

给定一系列点 \(x_1, x_2, \ldots, x_n\) 在数轴上。两个点 \(i\) 和 \(j\) 可以匹配，如果满足以下条件：\(i\) 和 \(j\) 都未被匹配。

You are given a set of pointsx1">x1x1,x2">x2x2, ...,xn">xnxnon the number line.

Two pointsi">iiandj">jjcan be matched with each other if the following conditions hold:

• neitheri">iinorj">jjis matched with any other point;
• |xi−xj|≥z">|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 integersn">nnandz">zz(2≤n≤2⋅105">2≤n≤2⋅1052≤n≤2⋅105,1≤z≤109">1≤z≤1091≤z≤109) — the number of points and the constraint on the distance between matched points, respectively.

The second line containsn">nnintegersx1">x1x1,x2">x2x2, ...,xn">xnxn(1≤xi≤109">1≤xi≤1091≤xi≤109).

Output

Print one integer — the maximum number of pairs of points you can match with each other.

Examples

Input

4 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 point1">11with point2">22(|3−1|≥2">|3−1|≥2|3−1|≥2), and point3">33with point4">44(|7−3|≥2">|7−3|≥2|7−3|≥2).

In the second example, you may match point1">11with point3">33(|5−10|≥5">|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; }