给定一个 $1$ 到 $n$ 的排列 $\pi$，$\pi$ 中的一个区间是指由连续数字组成的连续子序列。更准确地说，对于满足 $1 \le a \le b \le n$ 的下标 $a$ 和 $b$，如果子序列 $\pi_a^b = (\pi_a, \pi_{a+1}, \dots, \pi_b)$ 排序后能得到一个连续整数序列，则称其为一个区间。例如，在排列 $\pi = (3, 1, 7, 5, 6, 4, 2)$ 中，子序列 $\pi_3^6$ 是一个区间（它包含 $4$ 到 $7$ 的数字），而 $\pi_1^3$ 则不是。

对于子序列 $\pi_x^y$，其固有区间（intrinsic interval）是指任何包含该给定子序列（即 $a \le x \le y \le b$）且长度尽可能短的区间 $\pi_a^b$。当然，区间的长度定义为它所包含的元素个数。

给定一个排列 $\pi$ 和 $m$ 个子序列，请为每个子序列找到一个固有区间。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)，表示排列 $\pi$ 的大小。下一行包含 $n$ 个不同的整数 $\pi_1, \pi_2, \dots, \pi_n$ ($1 \le \pi_j \le n$)，即排列本身。

接下来一行包含一个整数 $m$ ($1 \le m \le 100\,000$)，表示子序列的数量。接下来的 $m$ 行中，第 $j$ 行包含整数 $x_j$ 和 $y_j$ ($1 \le x_j \le y_j \le n$)，表示第 $j$ 个子序列的端点。

输出格式

输出 $m$ 行。第 $j$ 行应包含两个整数 $a_j$ 和 $b_j$ ($1 \le a_j \le b_j \le n$)，表示第 $j$ 个子序列 $\pi_{x_j}^{y_j}$ 的某个固有区间的端点。

样例

输入 1

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

输出 1

3 6
7 7
1 7

输入 2

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

输出 2

1 4
3 7
3 7
3 10
7 10