题目描述

给一个长度为 $n$ 的序列 $a$。

$m$ 组询问，每次询问一个区间 $[l,r]$，是否存在一个数在 $[l,r]$ 中出现的次数大于 $\frac {r - l + 1} 2$。如果存在，输出这个数，否则输出 $0$。

输入格式

第一行两个数 $n,m$。

第二行 $n$ 个数 $a[i]$。

接下来 $m$ 行，每行两个数 $l,r$，表示询问 $[l,r]$这个区间。

输出格式

$m$ 行，每行对应一个答案。

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

1
0
3
0
4

提示

$n,m \le 5 \times 10^5,a[i] \le n$

题目来源

By Dzy