题目描述

译自 POI 2014 Stage 1. 「Couriers」

给定长度为 $n$ 的正整数序列。有 $m$ 组查询，每次查询区间 $[a,b]$ 中出现次数严格大于一半的数。

输入格式

第一行两个整数 $n, m$ ($1 \le n,m \le 500\,000$)，表示序列的长度和询问的个数。

接下来一行 $n$ 个整数 $p_1, p_2, \dots, 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$。