4439: 「POI2014」代理商 Couriers
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
**译自 POI 2014 Stage 1. 「[Couriers](https://szkopul.edu.pl/problemset/problem/Cs38m8lWFnOfDskXf43HR3lN/site/?key=statement)」**
给定长度为 $n$ 的正整数序列。
有 $m$ 组查询，每次查询区间 $[a,b]$ 中出现次数严格大于一半的数。
输入
第一行两个整数 $n,m (1 \le n,m \le 500\ 000)$，表示序列的长度和询问的个数。
接下来一行 $n$ 个整数 $p_1, p_2, ..., p_n (1 \le p_i \le n)$，表示该序列。
接下来 $m$ 行，每行两个整数 $a,b (1 \le a \le b \le n)$，表示查询从第 $a$ 个数到第 $b$ 个数之间（包括两个数本身）出现次数严格大于一半的数，如果没有则输出 $0$.
输出
输出 $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提示
数据范围：对于 $30\%$ 的数据，保证 $n,m \le 5000$. 对于 $65\%$ 的数据，保证 $n,m \le 5\times 10^4$. 对于所有数据，保证 $n,m \le 5\times 10^5$.