Question
Sum Pairs
In a treasure vault, you have a list B of N gems, each with a specific value. Your task is to count how many pairs of gems can be chosen such that the sum of their values lies between a minimum threshold M and a maximum threshold S. Formally, find the number of index pairs (i, j) where 1 ≤ i < j ≤ N and M ≤ Bi + Bj ≤ S.
Input
The first line of the input contains a single integer N.
The second line of the input contains two integers M and S.
The third line of the input contains N space-separated integers.
Constraints
2 ≤ N ≤ 105
1 ≤ L ≤ R ≤ 109
1 ≤ Ai ≤ 109
The second line of the input contains two integers M and S.
The third line of the input contains N space-separated integers.
Constraints
2 ≤ N ≤ 105
1 ≤ L ≤ R ≤ 109
1 ≤ Ai ≤ 109
Output
Print the count of pairs of elements in the array such that their sum is at least M and at most S.
Example
Sample Input
5 5 8
5 1 2 4 3
Sample Output
7
Explanation
The pairs of indices are as follows:
(1, 2) -> 5 + 1 = 6
(1, 3) -> 5 + 2 = 7
(1, 5) -> 5 + 3 = 8
(2, 4) -> 1 + 4 = 5
(3, 4) -> 2 + 4 = 6
(3, 5) -> 2 + 3 = 5
(4, 5) -> 4 + 3 = 7
All these sums are within range [M, S].
5 5 8
5 1 2 4 3
Sample Output
7
Explanation
The pairs of indices are as follows:
(1, 2) -> 5 + 1 = 6
(1, 3) -> 5 + 2 = 7
(1, 5) -> 5 + 3 = 8
(2, 4) -> 1 + 4 = 5
(3, 4) -> 2 + 4 = 6
(3, 5) -> 2 + 3 = 5
(4, 5) -> 4 + 3 = 7
All these sums are within range [M, S].