Byteasar 在 BAJ 公司工作，该公司销售电脑游戏。BAJ 公司与多家快递公司合作，将售出的游戏配送给客户。Byteasar 正在审查 BAJ 公司与各快递公司的合作情况。他有一份包裹配送记录，其中指明了每个包裹是由哪家快递公司配送的。他想确保没有任何一家快递公司在竞争中占据不公平的优势。

如果某家快递公司在一段时间内配送的包裹数量超过了该时段内总包裹数的一半，我们就称该公司在该时段内占据了主导地位。Byteasar 想找出在某些特定时间段内占据主导地位的快递公司（如果有的话）。

请帮助 Byteasar！编写一个程序，确定占据主导地位的快递公司，或者判断不存在这样的公司。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 500\,000$)，用空格隔开，分别表示 BAJ 公司发运的包裹总数和需要查询主导快递公司的时间段数量。快递公司的编号为 $1$ 到（最多）$n$。

输入的第二行包含 $n$ 个整数 $p_{1}, p_{2}, \dots, p_{n}$ ($1 \le p_{i} \le n$)，用空格隔开；$p_{i}$ 表示配送第 $i$ 个包裹的快递公司编号（按发运时间顺序）。

接下来的 $m$ 行每行描述一个时间段查询。每个查询由两个整数 $a$ 和 $b$ ($1 \le a \le b \le n$) 组成，用空格隔开。这表示需要确定在第 $a$ 个包裹到第 $b$ 个包裹（包含第 $a$ 个和第 $b$ 个）的配送期间占据主导地位的快递公司。

输出格式

对于每个查询，应在标准输出中打印一行结果。总共应打印 $m$ 行。每行应包含一个整数：在该时间段内占据主导地位的快递公司编号，如果不存在这样的公司，则输出 0。

样例

输入 1

7 5
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6

输出 1

1
0
3
0
4