[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]$。

Given a permutation $\pi$ of integers $1$ through $n$, an interval in $\pi$ is a consecutive subsequence consisting of consecutive numbers. More precisely, for indices $a$ and $b$ where $1 \le a \le b \le n$, the subsequence $\pi^b_a = (\pi_a, \pi_{a+1}, . . . ,\pi_b)$ is an interval if sorting it would yield a sequence of consecutive integers. For example, in permutation $\pi = (3, 1, 7, 5, 6, 4, 2)$, the subsequence $\pi^6_3$ is an interval (it contains the numbers $4$ through $7$) while $\pi^3_1$ is not. For a subsequence $\pi^y_x$ its intrinsic interval is any interval $\pi^b_a$ that contains the given subsequence $(a \le x \le y \le b)$ and that is, additionally, as short as possible. Of course, the length of an interval is defined as the number of elements it contains. Given a permutation $\pi$ and $m$ of its subsequences, find some intrinsic interval for each subsequence.

The first line contains an integer $n(1 \le n \le 100 000)$ — the size of the permutation $\pi$. The following line contains $n$ different integers $\pi_1, \pi_2, . . . , \pi_n (1 \le \pi_j \le n)$ — the permutation itself. The following line contains an integer $m(1 \le m \le 100 000)$ — the number of subsequences. The $j-th$ of the following $m$ lines contains integers $x_j$ and $y_j(1 \le x_j \le y_j \le n)$ — the endpoints of the $j-th$ subsequence.

Output $m$ lines. The $j-th$ line should contain two integers $a_j$ and $b_j$ where $1 \le a_j \le b_j \le n$ — the endpoints of some intrinsic interval of the $j-th$ subsequence $\pi^{y_j}_{x_j}$.

7
3 1 7 5 6 4 2
3
3 6
7 7
1 3

3 6
7 7 
1 7

10
2 1 4 3 5 6 7 10 8 9
5
2 3
3 7
4 7
4 8
7 8

1 4
3 7
3 7
3 10
7 10