배구

체육 시간에 Foma가 중요한 일로 학교를 나가야 했다. 아이들이 학교 안을 돌아다니다가 그의 부재를 들키지 않도록, 그는 학생들에게 과제를 냈다.

학교 부지에 기둥 $n$개가 1미터 간격으로 일렬로 서 있다. $i$번째 기둥의 높이는 $a_i$이다. 두 기둥의 높이가 같고 그 사이에 더 높은 기둥이 없으면, 두 기둥 사이에 배구 네트를 칠 수 있다. 학생마다 기둥 구간이 하나씩 주어지고, 학생은 그 구간에서 칠 수 있는 네트 중 가장 긴 것의 길이를 구해야 한다. 네트의 길이는 네트가 걸린 두 기둥 사이의 거리이다.

학생들은 이 문제를 푸는 데 시간이 많이 걸릴 것을 알고 도움을 요청했다.

첫 줄에 두 정수 $n$과 $m$이 주어진다 ($1 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$). 각각 기둥의 개수와 학생의 수이다. 둘째 줄에는 기둥의 높이 $a_1, a_2, \ldots, a_n$이 주어진다 ($1 \le a_i \le 10^9$). 다음 $m$개의 줄에는 각각 두 정수 $l$과 $r$이 주어진다 ($1 \le l \le r \le n$). 이는 한 학생에게 배정된 구간이다.

$m$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 학생의 답을 출력한다.