C. Number of Pairs-Codeforces Round ＃725 (Div. 3)

C. Number of Pairs

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array aa of nn integers. Find the number of pairs (i,j)(i,j) (1≤i<j≤n1≤i<j≤n) where the sum of ai+ajai+aj is greater than or equal to ll and less than or equal to rr (that is, l≤ai+aj≤rl≤ai+aj≤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 (4≤5+1≤74≤5+1≤7);
• i=1i=1 and j=3j=3 (4≤5+2≤74≤5+2≤7).

Input

The first line contains an integer tt (1≤t≤1041≤t≤104). Then tt test cases follow.

The first line of each test case contains three integers n,l,rn,l,r (1≤n≤2⋅1051≤n≤2⋅105, 1≤l≤r≤1091≤l≤r≤109) — the length of the array and the limits on the sum in the pair.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109).

It is guaranteed that the sum of nn overall test cases does not exceed 2⋅1052⋅105.

Output

For each test case, output a single integer — the number of index pairs (i,j)(i,j) (i<ji<j), such that l≤ai+aj≤rl≤ai+aj≤r.

Example

input

Copy

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

output

Copy

2
7
0
1

---

The title has a point that brings people to the pit , That's it i<j, People dare not sort , Actually, think about it carefully , After the sorting ,a And a There is only a size relationship , The original order relation does not need at all ; Assume that the previous original number is greater than the following , What's ahead j Just go , vice versa . Who does it i,j Are all the same , there i<j Just let you not repeat the choice (i,j)(j,i) nothing more .

After sorting , For each of these a[i], Want to find l-a[i] To r-a[i] The number of ,lower_bound Find the first one greater than or equal to l-a[i] The location of

upper_bound Find the first one greater than r-a[i] The location of （ The former must be within a reasonable range ）

To prevent repetition , namely a[i] Can find l-a[i] And r-a[i] Number between , Then you can also find a[i], So from i+1 Start looking for .

#include<iostream>
# include<cstring>
# include<algorithm>
# include<math.h>
# include<cmath>
# include<map>
using namespace std;
typedef long long int ll;
ll a[100000*2+10];
int main()
{

    int t;
    cin>>t;

    while(t--)
    {

        int n;
        ll l,r;
        scanf("%d%lld%lld",&n,&l,&r);

        for(int i=1; i<=n; i++)
        {
            scanf("%lld",&a[i]);
        }
        sort(a+1,a+1+n);
        ll sum=0;
        for(int i=1; i<=n; i++)
        {


            ll cnt1=lower_bound(a+i+1,a+1+n,l-a[i])-a;
            ll cnt2=upper_bound(a+i+1,a+1+n,r-a[i])-a;
            sum+=(cnt2-cnt1);
        }

        cout<<sum<<'\n';

    }

}