Yuto と Platina は「非減少部分配列ゲーム」をプレイしようとしている。このゲームは長さ $N$ の配列 $A$ を用いて行われる。

まず Yuto が整数を1つ言い、その後に Platina が整数を1つ言う。プレイヤーが選ぶ数は $L$ から $R$ までの範囲（両端を含む）でなければならない。選ばれた2つの整数を $a, b$ とし、$a \le b$ となるように順序付ける。このとき、ゲームのスコアは $a \le i \le j \le b$ を満たし、かつ区間 $[i, j]$ が配列 $A$ において非減少部分配列となっているような組 $(i, j)$ の個数となる。

区間 $[i, j]$ が非減少部分配列であるとは、$i \le x \le y \le j$ を満たすすべての $x, y$ に対して $A[x] \le A[y]$ が成り立つことを指す。

Yuto はスコアを最小化したいと考え、Platina はスコアを最大化したいと考えている。このゲームは非常に面白いため、$T$ 回プレイすることになった。すべてのゲームで同じ配列 $A$ を使用するが、ゲームごとに異なる $L$ と $R$ の値が与えられる場合がある。

両プレイヤーが最適に行動すると仮定したとき、各ゲームで得られるスコアを求めよ。

入力

1行目には2つの整数 $N$ と $T$ ($1 \le N, T \le 500\,000$) が与えられる。これらはそれぞれ配列の長さとゲームの回数を表す。

2行目には配列の値 $A[1], A[2], A[3], \dots, A[N]$ が与えられる ($1 \le A[i] \le 10^9$)。

続く $T$ 行の各行には、各ゲームの $L$ と $R$ を表す2つの正の整数 $L_i$ と $R_i$ ($1 \le L_i \le R_i \le N$) が与えられる。

出力

各ゲームについて、そのゲームのスコアをそれぞれ別の行に出力せよ。

入出力例

入力 1

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

出力 1

4
1
4
7
3