#P1538C. Number of Pairs

    ID: 572 Type: RemoteJudge 2000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>binary searchdata structuresmathtwo pointers*1300

Number of Pairs

No submission language available for this problem.

Description

You are given an array aa of nn integers. Find the number of pairs (i,j)(i, j) (1i<jn1 \le i < j \le n) where the sum of ai+aja_i + a_j is greater than or equal to ll and less than or equal to rr (that is, lai+ajrl \le a_i + a_j \le r).

For example, if n=3n = 3, a=[5,1,2]a = [5, 1, 2], l=4l = 4 and r=7r = 7, then two pairs are suitable:

  • i=1i=1 and j=2j=2 (45+174 \le 5 + 1 \le 7);
  • i=1i=1 and j=3j=3 (45+274 \le 5 + 2 \le 7).

The first line contains an integer tt (1t1041 \le t \le 10^4). Then tt test cases follow.

The first line of each test case contains three integers n,l,rn, l, r (1n21051 \le n \le 2 \cdot 10^5, 1lr1091 \le l \le r \le 10^9) — the length of the array and the limits on the sum in the pair.

The second line contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (1ai1091 \le a_i \le 10^9).

It is guaranteed that the sum of nn overall test cases does not exceed 21052 \cdot 10^5.

For each test case, output a single integer — the number of index pairs (i,j)(i, j) (i<ji < j), such that lai+ajrl \le a_i + a_j \le r.

Input

The first line contains an integer tt (1t1041 \le t \le 10^4). Then tt test cases follow.

The first line of each test case contains three integers n,l,rn, l, r (1n21051 \le n \le 2 \cdot 10^5, 1lr1091 \le l \le r \le 10^9) — the length of the array and the limits on the sum in the pair.

The second line contains nn integers a1,a2,,ana_1, a_2, \ldots, a_n (1ai1091 \le a_i \le 10^9).

It is guaranteed that the sum of nn overall test cases does not exceed 21052 \cdot 10^5.

Output

For each test case, output a single integer — the number of index pairs (i,j)(i, j) (i<ji < j), such that lai+ajrl \le a_i + a_j \le r.

Samples

Sample Input 1

4
3 4 7
5 1 2
5 5 8
5 1 2 4 3
4 100 1000
1 1 1 1
5 9 13
2 5 5 1 1

Sample Output 1

2
7
0
1