时间限制：1秒　　内存限制：256M

---

【问题描述】

　　给出一个非降序排列的整数数组：\(a[1],a[2],…,a[n]（-100 000≤a[i]≤100 000）\)，你的任务是对于一系列查询 \([i,j]\)，回答 \(a[i],a[i+1],…,a[j]\) 中出现次数最多的数值所出现的次数。

【输入格式】

　　输入包含多组数据。每组数据第一行为两个整数 \(n,q\)。
　　第二行包含 \(n\) 个非降序列的整数 \(a[1],a[2],…,a[n]\)。
　　以下 \(q\) 行每行包含两个整数 \(i\) 和 \(j(1≤i≤j≤n)\)。输入结束标志为 \(n=0\)。

【输出格式】

　　对于每个查询，输出查询结果。

【输入输出样例】

　Input

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

　Output

1
4
3 

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n,q≤100000\)。

【来源】

　　Mr.he