题目描述

小图打败了很多的怪兽并且得到了 $n$ 块宝石。他给每块宝石标记了序号（从 $1$ 到 $n$ ）。第 $i$ 块宝石的价值为 $v_i$。小图想要对这些宝石做 $2$ 类统计：

1. 请统计第 $l$ 块宝石到第 $r$ 块宝石的总价值。
2. 按照宝石价值从小到大排序后，再给宝石重新做序号标记（从 $1$ 到 $n$），统计第 $l$ 块宝石到第 $r$ 块宝石的总价值。

对于每种统计你都要给出正确的答案，否则小图会生气。

输入格式

第 $1$ 行输入包含 $1$ 个整数 $n\ (1 ≤ n ≤ 10^5)$。

第 $2$ 行输入包含 $n$ 个整数 $v_i$，$1 ≤ v_i​ ≤ 10^9$，代表每块宝石的价值。

第 $3$ 行包含 $1$ 个整数 $m\ (1 ≤ m ≤ 10^5)$，代表小图的统计次数。

接下来的 $m$ 行，每行包含 $3$ 个整数：统计类型 $type$，$l$ 和 $r\ (1 ≤ l ≤ r ≤ n;\ 1 ≤ type ≤ 2)$，确定了统计所需的参数。如果统计类型 $type$ 为 $1$ 那么你应该给出第 $1$ 类统计的答案。否则输出第 $2$ 类统计的答案。

输出格式

共有 $m$ 行输出，每行包含 $1$ 个整数，对应小图每次要求统计的结果。注意结果可能是会超过 $32$ 位的整数类型。

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