题目描述

Coffee 的世界里也是有棒棒糖卖的，Coffee 买了 $n$ 只连着的棒棒糖。这 $n$ 只棒棒糖包裹在小塑料袋中，排成 一列，相邻的两只棒棒糖的塑料袋是接起来的。为了方便，我们把棒棒糖从左到右编号为$1\cdots n$。

每只棒棒糖有一种口味。第 $i$ 只的口味是 $c_i$。两只棒棒糖 $i,j$ 的口味相同，当且仅当 $c_i=c_j$。Coffee 对 $m$ 只棒棒糖总体口味的评价比较奇怪。如果这 $m$ 只棒棒糖中，有一种口味 $c_0$ 的数量严格大于总数的一半，那么 Coffee 认为这 $m$ 只棒棒糖主要是 $c_0$ 口味的。Coffee 知道，这里的 $c_0$ 如果存在就一定是唯一的。而当 $c_0$ 不存在时，Coffee 认为这 $m$ 只棒棒糖是混合口味的。

Coffee 暂时舍不得吃棒棒糖，它在想一些好玩的问题。如果考虑棒棒糖序列的一个连续子序列 $s\cdots t(1\leq s\leq t\leq n)$，包括棒棒糖 $s$ 和 $t$。那么这 $t-s+1$ 只棒棒糖的总体口味是什么呢？

Coffee有一堆这样的问题，一共 $m$ 个。第 $i$ 个问题是棒棒糖子序列 $s_i\cdots t_i$ 的总体口味，请你帮忙解决。

输入格式

第一行两个用空格隔开的整数，分别表示 $n,m$。

接下来 $n$ 行，每行一个整数，表示 $c_i$。

接下来 $m$ 行，每行两个整数，表示 $s_i,t_i$。

输出格式

$m$ 行，每行一个整数，表示每个询问的总体口味。如果总体口味为混合口味则输出 $0$。

5 3 
1 
2 
2
1
1
1 5
2 5
2 4

1
0
2

提示

样例解释 1

在第一个询问中，口味 $1$ 出现 $3$ 次，大于总数的一半，所以总体口味为 $1$。

在第二个询问中，没有一种口味出现次数大于总数的一半，所以为混合口味。

在第三个询问中，口味 $2$ 出现 $2$ 次，大于总数的一半，所以总体口味为 $2$。

数据范围

对于 $100\%$ 的数据，$1\leq n,m,c_i\leq 5\times 10^4$。