Problem Statement

There is a permutation $P=(P_1,\ P_2,\ \dots,\ P_N)$ of length $N$ consisting of the integers from $1$ to $N$.

Consider the following operation.

• $1.$ Initialize with $X=N+1,\ i=1$.
• $2.$ Simultaneously update $X\leftarrow \min(X,\ P_i),\ P_i\leftarrow \max(X,\ P_i)$.
• $3.$ If $i=N$, end the operation. Otherwise, update $i\leftarrow i+1$ and return to $2$.

Let $P_k=(P_{k,1},\ P_{k,2},\ \dots,\ P_{k,N})$ denote the sequence $P$ after applying the operation $k$ times to $P$.

You are given $Q$ queries. In the $i$-th query, $2$ integers $x_i,\ y_i\ (x_i < y_i)$ are given. Output $k$ such that $P_{x_i,k}=y_i$ (it can be shown that such a $k$ always exists).

Input

$N$
$P_1$ $P_2$ $\dots$ $P_N$
$Q$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_Q$ $y_Q$

• $1 \le N \le 10^5$
• $1 \le P_i \le N$
• If $i\neq j$, then $P_i \neq P_j$
• $1 \le Q \le 2 \times 10^5$
• $1 \le x_i< y_i \le N$
• All input values are integers

Output

Output $Q$ lines. On the $i$-th line, output $k$ such that $P_{x_i,k}=y_i$.

Print a newline at the end.

Sample

5
2 5 3 1 4
2
1 2
2 5

4
3

5
1 2 3 4 5
2
1 3
3 5

3
5

20
20 19 9 15 18 16 13 14 17 12 11 10 6 5 8 4 2 3 7 1
10
4 6
13 19
10 19
14 17
11 15
9 10
10 15
2 9
3 18
7 14

18
15
12
18
17
20
16
14
6
14