Вам задан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Найдите количество пар индексов $$$(i, j)$$$ ($$$1 \le i < j \le n$$$), для которых сумма $$$a_i + a_j$$$ больше или равна $$$l$$$ и меньше или равна $$$r$$$ (то есть $$$l \le a_i + a_j \le r$$$).
Например, если $$$n = 3$$$, $$$a = [5, 1, 2]$$$, $$$l = 4$$$ и $$$r = 7$$$, то подходят две пары:
В первой строке находится целое число $$$t$$$ ($$$1 \le t \le 10^4$$$). Далее следуют $$$t$$$ наборов входных данных.
В первой строке каждого набора входных данных находятся три целых числа $$$n, l, r$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le l \le r \le 10^9$$$) — количество чисел в массиве и ограничения на сумму в паре.
Во второй строке находится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — количество пар индексов $$$(i, j)$$$ ($$$i < j$$$), для которых $$$l \le a_i + a_j \le r$$$.
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
2 7 0 1
| Codeforces Round 725 (Div. 3) |
|---|
| Закончено |
