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