莫队怎么求区间众数，即：

给定一个长度为 $n$ 的数组 $a$，和 $m$ 个询问 $l,r$，每个询问输出 $[l,r]$ 中的众数。

样例

输入

6
3 3 1 3 2 1
3
1 3
3 3
5 6

输出

3
1
1