#2432. 「POI2014」代理商 Couriers

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

Source: COCI 2009/2010 Round 3, Task PATULJCI

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