A38689.定点の轰炸

偏心……？

JW 的父亲是一个轰炸机飞行员，一天，他接到一个任务：对城市 $F$ 轰炸 $Q$ 次！当然，任务远没有这么简单，对于第 $i$ 次轰炸任务，他需要在 $[l_i,r_i]$ 内选择一个整数点轰炸。JW 的父亲在执行任务前，偶然发现这是他好朋友的家乡。于是他私自决定了：轰炸最高的建筑的位置！（因为他好朋友的房子很矮）。而且，为了保护好朋友的房子，JW 的父亲都会等待人们重修好再进行下一次轰炸。但是，他不知道在每次任务应该轰炸哪个位置，于是请 JW 班里的天才——你来解决。

当然，这个问题太难了，于是，JW 的父亲把这个问题简化了一下：这个城市可以看作一条长为 $N$ 个线段，$i$ 点上是房子 $i$，高 $h_i$ 米，每次给出范围 $l,r$，求出 $[l,r]$ 中的点 $i$，使 $h_i$ 最大。

输入共 $N + Q + 1$ 行：

第一行是两个正整数 $N,Q$，表示房子个数和轰炸次数；

第二行有 $N$ 个正整数，第 $i$ 个数 $h_i$ 代表房子 $i$ 的高度；

接下来有 $Q$ 行，每行是两个正整数 $l,r$，表示可以选择的轰炸范围。

输出为 $Q$ 行：

第 $i$ 行只有一个正整数，表示对于轰炸 $i$，要选择的房子的编号。如果有多个解，输出最小的一个。

【数据保证】

对于所有数据，保证：

$1 \leq l \leq r \leq N \leq 3 \times 10^5$，$1 \leq Q \leq 10^6$,$1\leq h_i \leq 10^9$

测试点	$N\leq$
1~5	$10^3$
6~10	$3\times10^5$

本题测试点等分。

【样例解释】

本题无样例解释。