Description

Hh最近沉迷于学习数据结构，尤其是与线段树相关的数据结构。一天，Hh接触到了一种特殊线段树——主席树，通过查阅相关资料他得知：主席树，又名可持久化权值线段树，其主要用途是用来查找区间第k大的数，但是Hh在经过一天的努力学习之后并没有搞懂主席树到底是什么，所以，无奈之下Hh决定向你求助。接下来hh会给你一个长度为n的数组A，其中含有n个元素，每个元素都是一个在int范围内的整数，且A中的元素不会重复，之后Hh将询问你q次，每次询问Hh都会给你一个区间[l, r]，以及一个正整数k，你是任务是对于Hh的每次询问，都回答出在A数组中当前区间[l, r]内的第k大的数是多少。Hh想请你来解决这一问题。

以下是Hh给你的主席树的相关定义：

主席树的全称是可持续化权值线段树，是一种可以维护静态区间第K大(小)的高级数据结构。

主席树的主要思想就是：保存每次插入操作时的历史版本，以便查询区间第k大(小)。

因为主席树每次都要插入操作，所以是不能用堆式建树的（rt<<1,rt<<1|1），所以我们使用动态开点线段树，并用ls[]和rs[]保存当前节点的左右儿子。

联系前缀和，可以预处理达到O(1)的时间复杂度。我们发现主席树也满足这个性质，所以若需要统计[l,r]的信息，只需要O(1)查询sum[r]-sum[l-1]即可。

Input Format

第一行会输入一个正整数n(0 < n <= 1000)，接下来第二行会有n个整数，表示Hh给你的数组A，A中的所有元素都是在int范围内的整数，接下来的一行中会有一个正整数q(0 <= q <= 50)，表示q次询问，之后会有q行，每行中首先会有一个正整数k，之后的两个正整数l, r(0 < l <= r <= n)表示要查询的区间的左端点和右端点。题目保证k <= r - l + 1。题目有多组测试样例，请处理到文件结尾。

Output Format

输出包含q行，对于每次询问，输出一行，每行包含一个整数，依次对应每次询问的答案

5
6 8 1 4 0
5        
1 2 2    
2 1 2
3 2 5
1 5 5
1 1 5

8
6
1
0
8

Source

1816 Online Judge 10.100.0.232