AT_arc218_d [ARC218D] I like Increasing

$ (1,2,\dots,N) $ の順列 $ P=(P_1,P_2,\dots,P_N) $ が与えられます。 ここで、整数列 $ x=(x_1,x_2,\dots,x_k) $ に対して、 $ x $ の**スコア**を $ x_i < x_{i+1} $ を満たす $ i $ の個数と定めます。 以下のクエリを $ Q $ 回処理してください。 - $ 1 \le l \le r \le N $ を満たす正整数 $ l,r $ が与えられる。 $ X = (P_l,P_{l+1},\dots,P_r) $ に対して以下の問題を解け。 - $ X $ の空でない部分列における**スコア**の最大値を $ M $ とする。 $ X $ の空でない部分列のうち、**スコア**が $ M $ であるものの長さの最小値を求めよ。 部分列とは数列 $ A $ の部分列とは、 $ A $ の要素を $ 0 $ 個以上選んで削除し、残った要素を元の順序を保って並べた数列のことを指します。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ P_1\ P_2\ \dots\ P_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリは以下の形式で与えられる。 > $ l\ r $

$ Q $ 行出力せよ。 $ i $ 行目には $ \mathrm{query}_i $ の答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のクエリでは、 $ X = (2,1,4) $ です。**スコア**の最大値 $ M $ は $ (2,4),(1,4),(2,1,4) $ によって達成される $ 1 $ です。これらの長さの最小値は $ (2,4),(1,4) $ によって達成される $ 2 $ です。 $ 2 $ 番目のクエリでは、 $ X = (4,6,3,5),M = 2 $ です。 $ (4,6,3,5) $ が**スコア**が $ 2 $ であるものの長さの最小値 $ 4 $ を達成します。 $ 3 $ 番目のクエリでは、 $ X = (1),M = 0 $ です。 $ (1) $ が**スコア**が $ 0 $ であるものの長さの最小値 $ 1 $ を達成します。 $ 4 $ 番目のクエリでは、 $ X = (2,1,4,6,3,5),M = 3 $ です。 $ (2,4,6,3,5) $ が**スコア**が $ 3 $ であるものの長さの最小値 $ 5 $ を達成します。 ### Constraints - $ 1 \le N,Q \le 2 \times 10^5 $ - $ P $ は $ (1,2,\dots,N) $ の順列 - $ 1 \le l \le r \le N $ - 入力は全て整数