구간 최솟값 쿼리 (RMQ)

N개의 수로 이루어진 수열이 있다. M개의 쿼리 [L, R]에 대해 L번째부터 R번째 수 중 최솟값을 출력한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000)
둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다. (1 ≤ Ai ≤ 10^9)
다음 M개의 줄에 L과 R이 주어진다. (1 ≤ L ≤ R ≤ N)

출력

각 쿼리의 최솟값을 한 줄에 하나씩 출력한다.

예제 입력 1

5 3
3 1 4 1 5
1 3
2 5
1 5

예제 출력 1

1
1
1