P4747 [CERC2017] Intrinsic Interval

对于正整数 $1,2,3 \cdots n$ 的一个排列 $\pi$，若它的一个子串 $\pi[a..b]$ 排序后是连续正整数，则称 $\pi[a..b]$ 是一个“区间”。例如对排列 $pi={3,1,7,5,6,4,2}$，子串 $\pi[3..6]$ 是一个“区间”（因为它包含 $4,5,6,7$），$\pi[1..3]$ 则不是。 一个子串的“本征区间”是包含该子串的最短区间。“包含”是指：若 $\pi[x..y]$ 的本征区间是 $\pi[a..b]$，则 $a \le x \le y \le b$。 给定一个排列 $\pi$ 及其 $m$ 个子串，求每个子串的“本征区间”。

第一行一个整数 $n(1 \le n \le 100000)$。 第二行 $n$ 个整数，代表排列 $\pi$。 第三行一个整数 $m(1 \le m \le 100000)$。 此后 $m$ 行，每行两个整数 $x,y(1 \le x \le y \le n)$，代表子串 $\pi[x..y]$。

输出 $m$ 行，每行两个整数 $a,b(1 \le a \le b \le n)$，代表子串对应的本征区间 $\pi[a..b]$。