题目描述

译自 POI 2014 Stage 1. 「Couriers」

给定长度为 $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$.

样例

input

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

output

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$.