최솟값

정수 $N$개가 순서대로 주어진다($1 \le N \le 100{,}000$). 이 가운데 $a$번째 정수부터 $b$번째 정수까지에서 가장 작은 값을 찾는 것은 어렵지 않다. 하지만 이런 $a$, $b$ 쌍이 $M$개 주어지면 이야기가 달라진다($1 \le M \le 100{,}000$). 이 문제를 해결해 보자.

여기서 $a$번째는 입력된 순서로 $a$번째라는 뜻이다. 예를 들어 $a = 1$, $b = 3$이면 입력 순서대로 1번, 2번, 3번 정수 중에서 최솟값을 찾는다. 각 정수는 1 이상 1,000,000,000 이하다.

첫째 줄에 $N$과 $M$이 주어진다. 이어지는 $N$개의 줄에 정수가 한 줄에 하나씩 주어진다. 그다음 $M$개의 줄에 $a$와 $b$가 공백으로 구분되어 주어진다($1 \le a \le b \le N$).

$M$개의 줄에 입력받은 순서대로 각 $a$, $b$에 대한 답을 출력한다.