問題文

この問題は Range Counting (BASIC) と問題設定が同じですが，$N$ の制約が異なります．

長さ $N$ の正整数列 $A = (A_1, A_2, \dots, A_N)$ と，$2$ つの整数 $L, R$ が与えられます．

$1 \leq i \lt j \leq N$ を満たす整数の組 $(i, j)$ であって，$A_i + A_j$ の値が $L$ 以上 $R$ 以下であるものの個数を求めてください．

制約

• 入力はすべて整数
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq L \leq R \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる．

N L R
A_1 ... A_N

出力

答えを $1$ 行で出力せよ．

サンプル

4 9 13
4 5 9 2

3

すべてのペアを列挙すると，次の通りになります．

• $(A_1, A_2)$ : $A_1 + A_2 = 9$
• $(A_1, A_3)$ : $A_1 + A_3 = 13$
• $(A_1, A_4)$ : $A_1 + A_4 = 6$
• $(A_2, A_3)$ : $A_2 + A_3 = 14$
• $(A_2, A_4)$ : $A_2 + A_4 = 7$
• $(A_3, A_4)$ : $A_3 + A_4 = 11$

よって，このうち $9$ 以上 $13$ 以下のものは $3$ つあるので，$3$ が答えです．

4 2 2
1 1 1 1

6

すべてのペアが条件を満たします．

7 6 9
3 1 4 1 5 9 2

7