Intrinsic Interval

You are given a permutation $\pi$ of the integers $1$ through $n$. For indices $a$ and $b$ with $1 \le a \le b \le n$, the consecutive subsequence $\pi_{ab} = (\pi_a, \pi_{a+1}, \dots, \pi_b)$ is an interval if sorting it yields a run of consecutive integers. For example, in the permutation $\pi = (3, 1, 7, 5, 6, 4, 2)$ the subsequence $\pi_{36}$ is an interval because it holds the numbers $4$ through $7$, while $\pi_{13}$ is not.

The intrinsic interval of a subsequence $\pi_{xy}$ is the shortest interval $\pi_{ab}$ that contains it, so $a \le x \le y \le b$. The length of an interval is the number of elements in it. Such a shortest interval is always unique. The intersection of two overlapping intervals is again an interval, so the intersection of all intervals containing $\pi_{xy}$ is itself an interval, and that intersection is the intrinsic interval.

You are given $\pi$ and $m$ of its subsequences. Find the intrinsic interval of each subsequence.

The first line contains the size $n$ ($1 \le n \le 100000$) of the permutation $\pi$. The second line contains $n$ different integers $\pi_1, \pi_2, \dots, \pi_n$ ($1 \le \pi_j \le n$), the permutation itself.

The third line contains the number of subsequences $m$ ($1 \le m \le 100000$). The $j$-th of the following $m$ lines contains the endpoints $x_j$ and $y_j$ ($1 \le x_j \le y_j \le n$) of the $j$-th subsequence.

Print $m$ lines. The $j$-th line must contain the endpoints $a_j$ and $b_j$ ($1 \le a_j \le b_j \le n$) of the intrinsic interval of the subsequence $\pi_{x_j y_j}$, separated by a space.