Kuriyama Mirai's Stones

# 宝石的价值 #### 题目 小图打败了很多的怪兽并且得到了 n 块宝石。他给每块宝石标记了序号（从 1 到 n ）。第 i 块宝石的价值为 vi 。小图想要对这些宝石做2类统计： 1.请统计第 l 块宝石到第 r 块宝石的总价值。(1 ≤ l ≤ r ≤ n) ，也就是求 。 2.按照宝石价值从小到大排序后，再给宝石重新做序号标记（从 1 到 n），统计第 l 块宝石到第 r 块宝石的总价值。 对于每种统计你都要给出正确的答案，否则小图会生气。 #### 输入 第 1 行输入包含 1 个整数 n (1 ≤ n ≤ $10^5$)。第2行输入包含 n 个整数 : $v_1$,$v_2$​, ..., $v_n$​ (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位的整数类型。

Kuriyama Mirai has killed many monsters and got many (namely $ n $ ) stones. She numbers the stones from $ 1 $ to $ n $ . The cost of the $ i $ -th stone is $ v_{i} $ . Kuriyama Mirai wants to know something about these stones so she will ask you two kinds of questions: 1. She will tell you two numbers, $ l $ and $ r (1<=l<=r<=n) $ , and you should tell her . 2. Let $ u_{i} $ be the cost of the $ i $ -th cheapest stone (the cost that will be on the $ i $ -th place if we arrange all the stone costs in non-decreasing order). This time she will tell you two numbers, $ l $ and $ r (1<=l<=r<=n) $ , and you should tell her . For every question you should give the correct answer, or Kuriyama Mirai will say "fuyukai desu" and then become unhappy.

The first line contains an integer $ n (1<=n<=10^{5}) $ . The second line contains $ n $ integers: $ v_{1},v_{2},...,v_{n} (1<=v_{i}<=10^{9}) $ — costs of the stones. The third line contains an integer $ m (1<=m<=10^{5}) $ — the number of Kuriyama Mirai's questions. Then follow $ m $ lines, each line contains three integers $ type $ , $ l $ and $ r (1<=l<=r<=n; 1<=type<=2) $ , describing a question. If $ type $ equal to $ 1 $ , then you should output the answer for the first question, else you should output the answer for the second one.

Print $ m $ lines. Each line must contain an integer — the answer to Kuriyama Mirai's question. Print the answers to the questions in the order of input.

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

Please note that the answers to the questions may overflow 32-bit integer type.