Close Matchups

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 128M

Problem type

The annual iceberg-hopping tournament is about to begin!

As the organizer of the tournament, your goal is to make the tournament as exciting as possible. Penguins don't like to watch boring games, so the closer the competitor's skills the better. More specifically, a matchup is considered exciting when the difference of skill between two competitors is less than or equal to \(K\).

Given \(N\) penguins each with a skill level of \(A_i\), what is the number of unordered pairs that will produce an exciting matchup?

Input Specification

The first line of the input will contain two integers \(N\) and \(K\) \((1 \le N \le 10^5, 0 \le K \le 10^9)\), indicating the number of penguins and the maximum difference of skill for an exciting matchup.

The next line of the input will each contain \(N\) integers representing the individual skill level of the \(N\) penguins, ranging from \(0\) to \(10^9\) inclusive.

Output Specification

Output an integer, representing the number of unordered pairs that will produce an exciting matchup.

Sample Input 1

5 1
2 1 0 1 3

Sample Output 1


Sample Explanation 1

The \(6\) exciting matchups are \((2, 1)\), \((2, 1)\), \((2, 3)\), \((1, 0)\), \((1, 1)\), and \((0, 1)\).


There are no comments at the moment.