Наклейки за диапазон уровней

В школе выдали наклейки за участие в кружках. У каждого ученика есть целое число — его «уровень активности».

Завуч готовит отчёт. Для каждого запроса он выбирает два числа L и R и хочет узнать, сколько наклеек суммарно получили ученики, у которых уровень активности попадает в диапазон от L до R включительно.

Важно: сумма может не помещаться в 32-битный тип (как в некоторых языках программирования), потому что значений много и они большие.

Формат ввода

Первая строка: целое число n — количество учеников. Вторая строка: n целых чисел a1, a2, ..., an — уровни активности учеников. Третья строка: целое число q — количество запросов. Далее q строк: по два целых числа L и R.

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

Выведите q строк. В i-й строке выведите сумму всех aj, для которых L ≤ aj ≤ R, для i-го запроса.

Ограничения

• 1 ≤ n ≤ 100000
• 1 ≤ q ≤ 100000
• 0 ≤ aj ≤ 1000000000
• 0 ≤ L ≤ R ≤ 1000000000

Пример

Ввод:

5
1 2 2 7 10
3
2 2
1 6
8 10

Вывод:

4
5
10