Description

给定$n$ 个整数的非递减序列$a_1 , a_2 ,…, a_n ，$对每个索引$i$ 和$j$ 组成的查询$（1≤i ≤j ≤n ）$，都确定整数$a_i , …, a_j$ 中的最频繁值（出现次数最多的值）。

Format

Input

包含多个测试用例。每个测试用例都以两个整数 $n$ 和 $q$ 的行开始。

下一行包含 $n$ 个整数 $a_1, …, a_n$，对每个 $i ∈[1, n-1]$ 都满足 $a_i ≤a_{i+1}$。

以下 $q$ 行，每行都包含一个查询，由两个整数 $i$ 和 $j$ 组成$（1≤i ≤j ≤n ）$，表示查询的边界索引。

在最后一个测试用例后跟一个包含单个$0$的行。

数据范围：$1≤n ，q ≤100000，-100000≤a_i ≤100000，i ∈[1,n]$。

Output

对每个查询，都单行输出一个整数，表示给定范围内最频繁值的出现次数。

Samples

10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0

1
4
3

来源

POJ3368