Assignment

Time Limit
10s
Memory Limit
65536KB
Judge Program
Standard
Ratio(Solve/Submit)
16.00%(4/25)
Description:

Tom owns a company and he is the boss. There are n staffs which are numbered from 1 to n in this company, and every staff has a ability. Now, Tom is going to assign a special task to some staffs who were in the same group. In a group, the difference of the ability of any two staff is less than k, and their numbers are continuous. Tom want to know the number of groups like this.

Input:

In the first line a number T indicates the number of test cases. Then for each case the first line contain 2 numbers n, k (1<=n<=100000, 0<k<=10^9),indicate the company has n persons, k means maximum difference between abilities of staff in a group is less than k. second line contains integers:a[1],a[2],…,a[n](0<=a[i]<=10^9),indicate i-th staff’s ability.

Output:

For each test,output the number of groups.

Sample Input:
2
4 2
3 1 2 4
10 5
0 3 4 5 2 1 6 7 8 9
Sample Output:
5
28
Hint:

First Sample, the satisfied groups include:[1,1]、[2,2]、[3,3]、[4,4] 、[2,3]

Source:

2015 Multi-University Training Contest 1


Submit