CF433B.Kuriyama Mirai's Stones

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.

九条一海已经击败了许多怪物，并获得了许多（即 $n$ 个）石头。她将这些石头从 $1$ 到 $n$ 编号。第 $i$ 个石头的价值为 $v_i$。九条一海想了解这些石头的一些信息，因此她会向你提出两类问题：

1. 她会告诉你两个数 $l$ 和 $r$（满足 $1 \leq l \leq r \leq n$），你需要告诉她：
   。

2. 设 $u_i$ 表示第 $i$ 小的石头的价值（即把所有石头的价值按非递减顺序排列后，排在第 $i$ 位的值）。这次她仍会告诉你两个数 $l$ 和 $r$（满足 $1 \leq l \leq r \leq n$），你需要告诉她：
   。

对于每个问题，你都必须给出正确答案；否则九条一海会说“好烦啊”，然后变得不开心。

The first line contains an integer n (1 ≤ n ≤ 105). The second line contains n integers: _v_1, _v_2, ..., v__n (1 ≤ v__i ≤ 109) — costs of the stones.

The third line contains an integer m (1 ≤ m ≤ 105) — 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.

第一行包含一个整数 $n$（$1 ≤ n ≤ 10^5$）。第二行包含 $n$ 个整数：$v_1, v_2, ..., v_n$（$1 ≤ v_i ≤ 10^9$）——表示各石头的代价。

第三行包含一个整数 $m$（$1 ≤ m ≤ 10^5$）——表示Kuriyama Mirai提出的问题数量。随后是 $m$ 行，每行包含三个整数 $type$、$l$ 和 $r$（$1 ≤ l ≤ r ≤ n$；$1 ≤ type ≤ 2$），描述一个问题。若 $type = 1$，则需输出第一个问题的答案；否则需输出第二个问题的答案。

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.

输出 m 行。每行必须包含一个整数——即 Kuriyama Mirai 问题的答案。请按输入的顺序输出各问题的答案。

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

请注意，问题的答案可能超出 32 位整数类型范围。