고유 구간

$1$부터 $n$까지의 정수로 이루어진 순열 $\pi$가 있다. 인덱스 $a$와 $b$가 $1 \le a \le b \le n$을 만족할 때, 연속한 부분 수열 $\pi_{ab} = (\pi_a, \pi_{a+1}, \dots, \pi_b)$를 정렬한 결과가 연속한 정수의 나열이면 이 부분 수열을 구간이라고 부른다. 예를 들어 순열 $\pi = (3, 1, 7, 5, 6, 4, 2)$에서 $\pi_{36}$은 $4$부터 $7$까지를 담고 있으므로 구간이지만, $\pi_{13}$은 구간이 아니다.

부분 수열 $\pi_{xy}$의 고유 구간은 이 부분 수열을 포함하면서($a \le x \le y \le b$) 길이가 가장 짧은 구간 $\pi_{ab}$이다. 구간의 길이는 원소의 개수다. 이런 구간은 항상 하나뿐이다. 겹치는 두 구간의 교집합도 구간이므로, $\pi_{xy}$를 포함하는 모든 구간의 교집합이 곧 고유 구간이다.

순열 $\pi$와 그 부분 수열 $m$개가 주어진다. 각 부분 수열의 고유 구간을 구하라.

첫째 줄에 순열 $\pi$의 크기 $n$ ($1 \le n \le 100000$)이 주어진다. 둘째 줄에 서로 다른 정수 $\pi_1, \pi_2, \dots, \pi_n$ ($1 \le \pi_j \le n$), 즉 순열 자체가 주어진다.

셋째 줄에 부분 수열의 개수 $m$ ($1 \le m \le 100000$)이 주어진다. 이어지는 $m$개 줄 중 $j$번째 줄에는 $j$번째 부분 수열의 양 끝 인덱스 $x_j$와 $y_j$ ($1 \le x_j \le y_j \le n$)가 주어진다.

$m$개 줄을 출력한다. $j$번째 줄에는 부분 수열 $\pi_{x_j y_j}$의 고유 구간의 양 끝 인덱스 $a_j$와 $b_j$ ($1 \le a_j \le b_j \le n$)를 공백으로 구분해 출력한다.