CF433B Kuriyama Mirai's Stones

栗山未来已经杀死了许多怪物，并得到了许多（准确地说有 $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$），你需要回答 。 每个问题你都需要给出正确答案，否则栗山未来会说 “不愉快です” 并且变得不高兴。

第一行包含一个整数 $n$（$1 \leq n \leq 10^{5}$）。 第二行包含 $n$ 个整数：$v_{1}, v_{2}, ..., v_{n}$（$1 \leq v_{i} \leq 10^{9}$），即宝石的价格。 第三行包含一个整数 $m$（$1 \leq m \leq 10^{5}$），表示栗山未来的问题个数。接下来 $m$ 行，每行包含三个整数 $type, l, r$（$1 \leq l \leq r \leq n; 1 \leq type \leq 2$），描述一个问题。如果 $type=1$，你应该回答第一个问题，否则回答第二个问题。

输出 $m$ 行。每行包含一个整数，依次为栗山未来提出的每个问题的答案。请按输入顺序输出答案。

请注意，答案可能会超出 $32$ 位整数范围。 由 ChatGPT 5 翻译