Pair Count Below X - Classic Problems | Repovive

CLS47. Pair Count Below X

2s256 MB

Given $n$ integers and a limit $x$ , count pairs of indices $(i, j)$ with $i < j$ and $a_i + a_j \le x$ .

\begin{array}{l} n \quad x \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

count

Input

5 7
1 2 3 4 5

Explanation

The valid pairs are (1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), and (3,4), so the answer is 8.

Output

Input

4 0
-2 -1 1 3

Explanation

The pairs with total at most 0 are (-2,-1), (-2,1), (-2,3), and (-1,1).

Output

Input

3 1
5 6 7

Explanation

Every pair is greater than 1, so no pair is counted.

Output

Given $n$ integers and a limit $x$ , count pairs of indices $(i, j)$ with $i < j$ and $a_i + a_j \le x$ .

\begin{array}{l} n \quad x \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

count