Migrated from Lutece 2763 GAMERS的众数

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

GAMERS 的颜色当然是绿色啦。GAMERS 的编剧总是要从众多的狗血剧情中找出最绿色的剧情。但是编剧真的很贪心，他想知道各种的狗血剧情中最绿色的剧情，但是由于预算有限，于是他打算使用较小的最绿色剧情。
说人话：
给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及询问区间的最小众数。

Input

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

第二行输入 $n$ 个数字，第 $i$ 个数字为 $a_i$ ，以空格隔开。

接下来输入 $n$ 行询问，每行输入两个数字 $l$ 、$r$，以空格隔开。

表示查询位于 $[l, r]$ 的数字的众数。

Output

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

Samples

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

1
2
2
2

Constraints

$1 \leq n \leq 10 ^5, -2 ^ {31} \leq others, ans \leq 2^{31} - 1$

Resources

2022 UESTC ICPC Training for Data Structures