B. Камни Курияма Мираи
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Курияма Мираи убила много чудовищ и получила в награду много (а именно n) камней. Все камни Курияма Мираи пронумерованы от 1 до n. Цена i-го камня равняется vi. Курияма Мираи хочет узнать некоторую информацию о своих камнях, с этой целью она задает вам вопросы. Каждый вопрос имеет один из следующих видов:

  1. Она называет вам два числа, l и r (1 ≤ l ≤ r ≤ n), а вы должны сказать ей, чему равна сумма .
  2. Пусть ui равняется цене i-го по дешевизне камня (цена, которая будет на i-ом месте, если расположить все цены камней в порядке неубывания). На этот раз она называет вам два числа, l и r (1 ≤ l ≤ r ≤ n), а вы должны сказать ей, чему равна сумма .

Вам нужно ответить правильно на ее вопросы, или Курияма Мираи скажет «fuyukai desu» (яп. неприятно) и расстроится.

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

В первой строке записано целое число n (1 ≤ n ≤ 105). Во второй строке записано n целых чисел: v1, v2, ..., vn (1 ≤ vi ≤ 109) – цены камней.

В третьей строке записано целое число m (1 ≤ m ≤ 105) — количество вопросов Курияма Мираи. Затем следует m строк, в каждой строке записано три целых числа: type, l и r (1 ≤ l ≤ r ≤ n; 1 ≤ type ≤ 2), описывающих текущий вопрос. Если type равняется 1, то вам нужно вывести ответ на вопрос первого типа, в противном случае надо вывести ответ на вопрос второго типа.

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

Выведите m строк. В каждой строке должно быть записано целое число — ответ на вопрос Курияма Мираи. Выводите ответы на вопросы в порядке их следования во входных данных.

Примеры
Входные данные
6
6 4 2 7 2 7
3
2 3 6
1 3 4
1 1 6
Выходные данные
24
9
28
Входные данные
4
5 5 2 3
10
1 2 4
2 1 4
1 1 1
2 1 4
2 1 2
1 1 1
1 3 3
1 1 3
1 4 4
1 2 2
Выходные данные
10
15
5
15
5
5
2
12
3
5
Примечание

Пожалуйста, обратите внимание, что для хранения ответов на вопросы может быть не достаточно 32-битных целых чисел.