#CF433B. 栗山未来的石头
栗山未来的石头
CF433B Kuriyama Mirai's Stones
题目描述
栗山未来已经杀死了许多怪物,并得到了许多(准确地说有 个)宝石。她将这些宝石从 编号到 。第 个宝石的价格是 。栗山未来想知道这些宝石的一些信息,因此她会向你提出两种类型的问题:
她会告诉你两个数字 和 ,你需要回答 。
设 为第 便宜的宝石的价格(即把所有宝石的价格非递减排序后,排在第 位的价格)。这次她会告诉你两个数字 和 ,你需要回答 。
每个问题你都需要给出正确答案,否则栗山未来会说“不愉快です”并且变得不高兴。
输入格式
第一行输入一个整数 代表宝石的数量。
第二行输入 个整数 $v_1,v_2,\dots,v_n \left(1 \leqq v_i \leqq 10^9\right)$ 代表第 个宝石的价格。
第三行输入一个整数 代表问题的个数。
此后 行,第 行输入三个整数 $\mathrm{type},l,r \left(1 \leqq \mathrm{type} \leqq 2;\ 1 \leqq l \leqq r \leqq n\right)$ 描述一个问题。若 ,代表第一个问题;否则代表第二个问题。
输出格式
输出 行,第 行输出一个整数,代表栗山未来提出的第 个问题的答案。请按输入顺序输出答案。
测试样例
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
数据范围与提示
请注意,答案可能会超出 位整数范围。