В соревновании участвовали n участников, для каждого известен некоторый числовой результат. После завершения соревнования всех участников ранжируют по неубыванию результата.

Затем нужно ответить на q запросов. В каждом запросе заданы числа l и r, и требуется найти сумму результатов участников, занявших места с l-го по r-е включительно в списке после сортировки. Нумерация мест начинается с 1.

Для каждого запроса выведите соответствующую сумму.

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

Первая строка содержит целое число n — количество участников.

Во второй строке содержатся n целых чисел a_i — результаты участников.

В третьей строке содержится целое число q — количество запросов.

В следующих q строках содержатся пары целых чисел l, r — границы диапазона мест.

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

Для каждого запроса выведите одно целое число — сумму результатов участников, стоящих на позициях с l по r включительно после сортировки по неубыванию.

Каждый ответ выводите в отдельной строке.

Ограничения

• 1 <= n <= 2 * 10^5
• -10^9 <= a_i <= 10^9
• 1 <= q <= 2 * 10^5
• 1 <= l <= r <= n

Ответы могут не помещаться в 32-битный целочисленный тип.

Примеры

Пример 1

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

5
-1000000000 -999999999 -1 0 1
6
1 1
2 2
3 3
4 4
5 5
1 1

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

-1000000000
-999999999
-1
0
1
-1000000000

Пример 2

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

8
-1000000000 1000000000 -1000000000 1000000000 -1000000000 1000000000 -1000000000 1000000000
7
3 3
6 7
6 8
3 6
4 8
3 8
1 7

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

-1000000000
2000000000
3000000000
0
3000000000
2000000000
-1000000000