**PROBLEM LINK**

**DIFFICULTY**

Easy

**PREREQUISITES**

Simple Logic

**PROBLEM IN SHORT**

The problem statement is simplistic enough.

**SOLUTION**

The first thing to note is that we have to take the absolute value of the difference of the two

elements. This simply means that the order in which we discover the elements, (a_{i}, a_{j}) satisfying

the condition, (a_{i} - a_{j} >= k) doesn’t matter. Also, the constraints are small enough to allow sorting. So, we just sort the array.

Now that the array is sorted, we can naively check for the left most element a_{1} , how many a_{j}

satisfy the given condition. This can be done in O(n^2). But this is not good enough to pass the

second sub-task.

Taking it a step further - as the elements are sorted - we can see that a sliding window would do

the job in O(n) time.

In this, we’ll iterate over the array maintaining two indices, a and b starting from the leftmost part of the array. The basic aim is to find the first a[j] for a particular i, such that it’s the smallest element, where a[j] - a[i] >= k. This can be done by incrementing i, if a[j] - a[i] >= k, else increment j. For a particular I, the number of matching pairs will be N - j. The sum of matching elements for all i is the answer.

**TIME COMPLEXITY**

Sorting takes O(n log n), and the sliding window works in O(n) time, so overall complexity is O(n log n) which will pass the constraints.

**EDITORIALIST’s SOLUTION**

```
#include <bits/stdc++.h>
using namespace std;
int a[65007], n, k;
int main() {
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
sort(a, a + n);
long long ans = 0;
int i = 0, j = 0;
while (i < n) {
if (j < i)
j = i;
else if (j >= n)
break;
if (a[j] - a[i] >= k) {
i++;
ans += n - j;
}
else
j++;
}
printf("%lld", ans);
return 0;
}
```