As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

A wrestling match will be held tomorrow.  n  players will take part in it. The  i th player’s strength point is  ai .

If there is a match between the  i th player plays and the  j th player, the result will be related to  |ai−aj| . If  |ai−aj|>K , the player with the higher strength point will win. Otherwise each player will have a chance to win.

The competition rules is a little strange. Each time, the referee will choose two players from all remaining players randomly and hold a match between them. The loser will be be eliminated. After  n−1  matches, the last player will be the winner.

Now, Yuta shows the numbers  n,K  and the array  a  and he wants to know how many players have a chance to win the competition.

It is too difficult for Rikka. Can you help her?  

The first line contains a number  t(1≤t≤100) , the number of the testcases. And there are no more than  2  testcases with  n>1000 .

For each testcase, the first line contains two numbers  n,K(1≤n≤105,0≤K<109) .

The second line contains  n  numbers  ai(1≤ai≤109) .

For each testcase, print a single line with a single number -- the answer.

2017 Multi-University Training Contest - Team 5

liuyiding   |   We have carefully selected several similar problems for you:   6095  6094  6093  6092  6091 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int i,j,k,p,t;
    int n;
    int a[100001];
    int tot;
    cin>>t;
    while(t--)
    {
        cin>>n>>k;
        tot=1;
        for(i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        sort(a+1,a+n+1);
        for(i=n-1;i>=1;i--)
        {
            if(a[i+1]-a[i]<=k)tot++;
            else break;
        }
        cout<<tot<<endl;
    }
    return 0;
}