题目描述

简化题意： 给一个长度为 $n$ 的正整数序列 $a$。共有 $m$ 组询问，每次询问一个区间 $[l,r]$，是否存在一个数在 $[l,r]$ 中出现的次数严格大于一半。如果存在，输出这个数，否则输出 $0$。

---

Byteasar 在卖电脑游戏的 BAJ 公司上班。

BAJ 公司和多家快递公司合作，由这些快递公司将 BAJ 公司销售的游戏送给客户。

Byteasar 正在审查 BAJ 公司与快递公司的合作情况。

他有一份连续的包裹记录，每个包裹都注明了负责配送的快递公司。

他想确认没有任何一家快递公司比其他的具有不公平的优势。

如果在某个时间段内，某家快递公司配送了一半以上的包裹，我们就说它在该时间段内占主导地位。

Byteasar 想要知道在某些特定的时间段内，哪家快递公司占主导地位（如果存在的话）。

来帮 Byteasar 解决这个问题吧！

请编写一个程序，判断在给定时间段内占主导地位的快递公司，或者判断不存在这样的公司。

输入格式

第一行包含两个整数 $n,m$，用一个空格分隔，分别表示 BAJ 公司发货的包裹总数以及需要查询占主导地位的快递公司的时间段数量。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，用单个空格隔开，$a_i$ 表示配送第 $i$ 个包裹的快递公司编号（按照配送时间排序）。

接下来的 $m$ 行，每行指定对某个时间段的询问。

每个询问包含两个整数 $l$ 和 $r$，用一个空格分隔。这意味着需要确定，在第 $l$ 个包裹到第 $r$ 个包裹（包含这两个包裹）的发货期间，占主导地位的快递公司。

输出格式

输出 $m$ 行，每行包含一个整数，表示对于每个询问的时间段占主导地位公司的编号，如果不存在这样的公司则输出 $0$。

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

1
0
3
0
4

提示

数据范围

对于所有数据，$1 \le n,m \le 5 \times 10^5$，$1 \le a_i \le n$。