D. Подсчет количества пар
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана последовательность $$$a$$$, состоящая из $$$n$$$ целых чисел, причем $$$i$$$-е число последовательности равно $$$a_i$$$. Также вам заданы два целых числа $$$x$$$ и $$$y$$$ ($$$x \le y$$$).

Пара целых чисел $$$(i, j)$$$ считается интересной, если выполняются следующие условия:

  • $$$1 \le i < j \le n$$$;
  • если одновременно удалить из последовательности $$$a$$$ числа в позициях $$$i$$$ и $$$j$$$, то сумма оставшихся элементов должна быть не меньше $$$x$$$ и не больше $$$y$$$.

Перед вами стоит задача определить количество интересных пар целых чисел для заданной последовательности $$$a$$$.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк:

  • в первой строке заданы три целых числа $$$n, x, y$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$1 \le x \le y \le 2 \cdot 10^{14}$$$);
  • во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$).

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество интересных пар целых чисел для заданной последовательности $$$a$$$.

Пример
Входные данные
7
4 8 10
4 6 3 6
6 22 27
4 9 6 3 4 5
3 8 10
3 2 1
3 1 1
2 3 4
3 3 6
3 2 1
4 4 12
3 3 2 1
6 8 8
1 1 2 2 2 3
Выходные данные
4
7
0
0
1
5
6
Примечание

В первом примере существует $$$4$$$ интересных пары целых чисел:

  1. $$$(1, 2)$$$;
  2. $$$(1, 4)$$$;
  3. $$$(2, 3)$$$;
  4. $$$(3, 4)$$$.