Description

FZ酱有很多朋友，期末考试结束了，她邀请了\(n\)个朋友来聚会，FZ酱把她的朋友编号为\(1\)~\(n\)。
朋友们到来的时间有早有晚，FZ酱以自己到达的时刻记为\(0\)时刻，朋友到达的时刻就可以表示为他们与FZ酱到达时刻的差值。记时刻小于\(0\)为在FZ酱到达之前到达，大于\(0\)为在FZ酱到达之后到达。
所有朋友都到齐了，FZ酱很好奇朋友们的到达时间，她统计了这\(n\)个朋友的到达时间，发现这些数据有集中的趋势。想到数学课上学的一些知识，她想统计一下编号\([l,r]\)之内的朋友们什么时候来的最多。
由于FZ酱讨厌做数学题，于是她将这项工作推给了HSD桑，HSD桑看了一眼这些时刻，就将这项任务交给了你。你大喊道：“凭什么交给我啊！”可是HSD桑已经跑远了。所以请完成这项任务。

Format

Input

第\(1\)行两个正整数\(n\)和\(T\)，表示FZ酱的朋友数\(n\)和她希望调查的区间个数\(T\)。
第\(2\)行\(n\)个整数，第\(i\)个整数表示编号为\(i\)的朋友到达的时刻\(a_i\)。
第\(3\)~\(T+4\)行，每行两个正整数\(l\)，\(r\)，表示希望调查的区间\([l,r]\)。

Output

共\(T\)行，对于第\(i\)行输出为对第\(i\)个询问的答案。
如果有超过\(1\)个时刻到达的人数最多，请输出最小的时刻。

Sample

Input

10 5
1 1 3 3 1 2 3 1 2 3
1 10
2 5
6 9
3 10
7 10

Output

1
1
2
3
3

Explanation

对于\([1,10]\)中，在\(1\)时刻到达的共\(4\)人，在\(2\)时刻到达的共\(2\)人，在\(3\)时刻到达的共\(4\)人。在\(1\)、\(3\)时刻到达人数相同，所以答案为较小的时刻\(1\)；
对于\([2,5]\)中，在\(1\)时刻到达的共\(2\)人，在\(3\)时刻到达的共\(2\)人。在\(1\)、\(3\)时刻到达人数相同，所以答案为较小的时刻\(1\)；
对于\([6,9]\)中，在\(1\)时刻到达的共\(1\)人，在\(2\)时刻到达的共\(2\)人，在\(3\)时刻到达的共\(1\)人。所以答案为\(2\)；
对于\([3,10]\)中，在\(1\)时刻到达的共\(2\)人，在\(2\)时刻到达的共\(2\)人，在\(3\)时刻到达的共\(4\)人。所以答案为\(3\)；
对于\([7,10]\)中，在\(1\)时刻到达的共\(1\)人，在\(2\)时刻到达的共\(1\)人，在\(3\)时刻到达的共\(2\)人。所以答案为\(3\)。

Limitation

共\(10\)组测试数据，只有输出与标准输出完全相同才可以获得\(10\text{pts}\)。
对于每组测试数据，时间限制为2s，内存限制为512MiB。
对于一组特殊的\(10\%\)的数据，满足\(n\le 10^5\)，\(T=1\)，\(0\le a_i\le 10^5\)；
对于\(30\%\)的数据，满足\(n\le 10^3\)，\(T\le 10^3\)，\(0\le a_i\le 10^5\)；
对于\(60\%\)的数据，满足\(n\le 10^3\)，\(T\le 10^3\)，\(|a_i|\le 10^9\)；
对于\(100\%\)的数据，满足\(n\)，\(T\le 5\times 10^4\)，\(|a_i|\le 10^9\)，\(l\le r\)。

Source

Problem by HeRaNO