$(1, 2, \cdots, N)$ の順列 $P$ があり、時刻 $0$ の時点で $P = (P_1, P_2, \cdots, P_N)$ です。

各時刻 $t = 1, 2, 3, \cdots 10^{100}$ に以下の操作が行われます。

整数 $i$ を、 $i \equiv t ~ (\mathrm{mod} ~ N - 1)$ かつ $1 \leq i \leq N - 1$ を満たす値とする。
$P$ の $i$ 番目の値が $i + 1$ 番目の値よりも大きいならば、これらの値を入れ替える。そうでない場合、何も行わない。

$Q$ 個の独立した質問が与えられるので、それぞれについて答えてください。
$k ~ (1 \leq k \leq Q)$ 番目の質問は $X_k \lt Y_k$ を満たす整数の組 $(X_k, Y_k)$ を用いて以下のように説明されます。

次の条件をはじめて満たす時刻を求めてください。

• $P$ の $i$ 番目の値が $X_k$ 、 $j$ 番目の値が $Y_k$ であるとき、 $i < j$ である。

ただし、時刻 $0$ の時点ですでに条件を満たす場合、 $0$ と答えてください。

• $2 \leq N \leq 500{,}000$
• $1 \leq Q \leq 100{,}000$
• $(P_1, P_2, \cdots, P_N)$ は $(1, 2, \cdots, N)$ の順列
• $1 \leq X_k \lt Y_k \leq N$
• 入力はすべて整数

• $N \leq 2{,}000$ を満たすデータセットに正解した場合は $50$ 点が与えられる。

入力は以下の形式で標準入力から与えられる。

$N$ $Q$  
$P_1$ $P_2$ $\ldots$ $P_N$  
$X_1$ $Y_1$  
$X_2$ $Y_2$  
$\vdots$  
$X_Q$ $Y_Q$

$Q$ 行出力せよ。 $k ~ (1 \leq k \leq Q)$ 行目には $k$ 番目の質問についての答えを整数で出力せよ。