Description

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

Format

Input

包含多个测试用例。每个测试用例都以两个整数$n$和$q$$（1≤n ，q ≤100000）$的行开始。下一行包含$n$ 个整数$a_1$$, …, a_n（-100000≤a_i ≤100000，i ∈{1, …, n }）$。对每个$i ∈{1, …, n-1}，$都满足$a_i ≤a_{i+1}$。以下$q$行，每行都包含一个查询，由两个整数$i$ 和$j$ 组成$（1≤i ≤j ≤n ）$，表示查询的边界索引。在最后一个测试用例后跟一个包含单个$0$的行。

Output

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

Samples

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

1
4
3