최솟값과 최댓값

입력 순서대로 N개의 정수가 주어진다. N은 1 이상 100,000 이하이고, 각 정수는 1 이상 1,000,000,000 이하이다.

하나의 구간에 대해 a번째 정수부터 b번째 정수까지의 최솟값과 최댓값을 찾는 일은 어렵지 않다. 하지만 이러한 구간이 M개 주어진다면 효율적으로 처리해야 한다. M은 1 이상 100,000 이하이다.

여기서 a번째 정수란 입력된 순서에서 a번째에 나온 정수를 뜻한다. 예를 들어 a = 1, b = 3이면 입력된 1번, 2번, 3번 정수만을 대상으로 최솟값과 최댓값을 찾아야 한다.

첫째 줄에 N과 M이 주어진다.

다음 N개의 줄에는 정수가 하나씩 주어진다.

다음 M개의 줄에는 a와 b의 쌍이 주어진다.

질의가 주어진 순서대로 M개의 줄을 출력한다. 각 줄에는 해당 a, b에 대한 최솟값과 최댓값을 이 순서로 출력한다.