11235 - Frequent values

給定一個有 $n$ 個整數的數列 $a_1, a_2, \cdots{}, a_n$，且數列以非遞減的次序排列，並給定多組整數對 $i, j$ ($1\leq{i}\leq{j}\leq{n}$)，請你從 $a_i, \cdots{}, a_j$ 中找出出現次數最多的數值共出現幾次。

Input

輸入有多組測試資料，每組資料的第一列有兩個整數 $n, q$ ($1\leq{n, q}\leq{100000}$)。下一列有 $n$ 個以空白字元隔開的整數 $a_1, a_2, \cdots{}, a_n$ ($-100000\leq{a_i}\leq{100000}$，其中 $i$ 為 $1$ 到 $n$)，接下來有 $q$ 列每列表示一組 $i, j$。

最後一組測試資料以一列一個 0 表示測試資料結束。

Output

請對每次查詢的數對中找出其範圍內同一數值出現最多次的次數。

Sample Input

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

Sample Output

1
4
3