#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

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$ .

Constraints

$1 \le n \le 2 \cdot 10^5$
$-10^9 \le a_i, x \le 10^9$
The answer fits in a signed 64-bit integer.

Input

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

Output

count

Samples

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$ .

$1 \le n \le 2 \cdot 10^5$
$-10^9 \le a_i, x \le 10^9$
The answer fits in a signed 64-bit integer.

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

count