問題文

長さ $N$ で $1$ から $N$ までの整数からなる順列 $P=(P_1,\ P_2,\ \dots,\ P_N)$ があります。

次のような操作を考えます。

• $1.$ $X=N+1,\ i=1$ で初期化する
• $2.$ $X\leftarrow \min(X,\ P_i),\ P_i\leftarrow \max(X,\ P_i)$ で同時に更新する
• $3.$ $i=N$ ならば操作を終える。そうでないなら $i\leftarrow i+1$ と更新し、 $2$ に戻る。

$P$ に対し操作を $k$ 回適用したあとの数列 $P$ を $P_k=(P_{k,1},\ P_{k,2},\ \dots,\ P_{k,N})$ とします。

$Q$ 個のクエリが与えられます。 $i$ 番目のクエリでは $2$ つの整数 $x_i,\ y_i\ (x_i < y_i)$ が与えられるので $P_{x_i,k}=y_i$ を満たす $k$ を出力してください（このような $k$ は必ず存在することが示せます）。

入力

$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$
• $i\neq j$ ならば $P_i \neq P_j$
• $1 \le Q \le 2 \times 10^5$
• $1 \le x_i< y_i \le N$
• 与えられる入力はすべて整数

出力

$Q$ 行出力してください。 $i$ 行目には $P_{x_i,k}=y_i$ を満たす $k$ を出力してください。

最後に改行してください。

サンプル

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