| Codeforces Round 248 (Div. 2) |
|---|
| Закончено |
Курияма Мираи убила много чудовищ и получила в награду много (а именно n) камней. Все камни Курияма Мираи пронумерованы от 1 до n. Цена i-го камня равняется vi. Курияма Мираи хочет узнать некоторую информацию о своих камнях, с этой целью она задает вам вопросы. Каждый вопрос имеет один из следующих видов:
- Она называет вам два числа, l и r (1 ≤ l ≤ r ≤ n), а вы должны сказать ей, чему равна сумма
. - Пусть 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-битных целых чисел.
