P1021：数列分块入门 9

题目描述

给出一个长为 $n$ 的数列，以及 $n$ 个询问，操作涉及区间的最小众数。

这里的最小众数指在区间中出现次数最多的数里，数值最小的那个。

输入输出格式

输入

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数，第 $i$ 个整数为 $a_i$。

接下来输入 $n$ 行，每行输入两个整数 $l, r$，表示询问区间 $[l,r]$ 的最小众数。

输出

对于每次询问，输出一行一个整数表示答案。

样例

4
1 2 2 4
1 2
1 4
2 4
3 4

1
2
2
2

数据范围

• 对于 $100\%$ 的数据，$1 \le n \le 100000$。
• 其余输入数据及答案均在 $32$ 位有符号整数范围内。