EduBrick

Пары с суммой

1000 мс · 256 МБ · всё или ничего

Дан массив из nn чисел. Для каждого запроса xx посчитайте количество пар индексов i<ji < j, для которых ai+aj≤xa_i + a_j \le x.

Формат ввода

В первой строке nn (2≤n≤2⋅1052 \le n \le 2 \cdot 10^5). Во второй — nn чисел aia_i, по модулю не больше 10910^9.

В третьей строке qq (1≤q≤501 \le q \le 50). В четвёртой — qq запросов xx, по модулю не больше 2⋅1092 \cdot 10^9.

Формат вывода

Для каждого запроса выведите количество пар в отдельной строке.

Примеры

ввод
2
1 2
3
2 3 4
вывод
0
1
1
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.