問題文

数列 $B$ に対する【 問題 】を以下のように定義します。

【 問題 】

あなたは、以下の操作を何度でも行うことができます。

• $1 \leq l < r \leq | B |$ を満たす整数組 $(l, r)$ を選び、$(B_l, \ldots, B_{r-1}, B_r)$ を $(B_r, B_l, \ldots, B_{r-1})$ に置き換える。

$B$ を昇順に並べ替えるのに必要な最小の操作回数を求めてください。

さて、$(1, 2, \ldots, N)$ の順列 $A = (A_1, A_2, \ldots, A_N)$ が与えられます。

クエリが $Q$ 個与えられるため、順番に処理してください。$i$ 番目のクエリは以下の通りです。

• l r: 数列 $(A_l, A_{l+1}, \ldots, A_r)$ について【 問題 】を解き、その答えを出力する。

制約

• $1 \leq N, Q \leq 2 \times 10^{5}$
• $1 \leq A_i \leq N$
• $i \neq j \implies A_i \neq A_j$
• $1 \leq l \leq r \leq N$
• 入力はすべて整数である。

入力

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

$N$ $Q$
$A_1$ $A_2$ $\cdots$ $A_N$
query $1$  
query $2$  
$\vdots$

query $Q$ 

各クエリは以下に示す形式で与えられる。

l r

出力

$Q$ 行出力せよ。

$i$ 行目には、$i$ 番目のクエリに対する答えを出力せよ。

サンプル

5 4
4 2 3 1 5
1 3
1 4
2 5
5 5

2
3
1
0