D - I like Increasing 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 700 点

問題文

(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 個以上選んで削除し、残った要素を元の順序を保って並べた数列のことを指します。

制約

  • 1 \le N,Q \le 2 \times 10^5
  • P は (1,2,\dots,N) の順列
  • 1 \le l \le r \le N
  • 入力は全て整数

入力

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

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 の答えを出力せよ。

入力例 1

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

出力例 1

2
4
1
5

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 を達成します。

入力例 2

12 8
8 3 5 7 9 6 11 1 10 4 12 2
3 4
10 11
5 8
3 8
4 10
2 10
5 7
1 8

出力例 2

2
2
2
4
5
7
2
5

Score : 700 points

Problem Statement

You are given a permutation P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N).

For a sequence of integers x=(x_1,x_2,\dots,x_k), define the score of x as the number of indices i satisfying x_i < x_{i+1}.

Process the following query Q times.

  • You are given positive integers l and r with 1 \le l \le r \le N. For X = (P_l,P_{l+1},\dots,P_r), solve the following problem.
    • Let M be the maximum score of a non-empty subsequence of X. Find the minimum length of a non-empty subsequence of X whose score equals M.
What is a subsequence? A subsequence of a sequence A is a sequence obtained by removing zero or more elements from A and arranging the remaining elements in their original order.

Constraints

  • 1 \le N,Q \le 2 \times 10^5
  • P is a permutation of (1,2,\dots,N).
  • 1 \le l \le r \le N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
P_1\ P_2\ \dots\ P_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in the following format:

l\ r

Output

Output Q lines. The i-th line should contain the answer to \mathrm{query}_i.

Sample Input 1

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

Sample Output 1

2
4
1
5

For the first query, X = (2,1,4). The maximum score M = 1 is achieved by (2,4),(1,4),(2,1,4). The minimum length among these is 2, achieved by (2,4),(1,4).

For the second query, X = (4,6,3,5) and M = 2. (4,6,3,5) achieves the minimum length 4 among those with score 2.

For the third query, X = (1) and M = 0. (1) achieves the minimum length 1 with score 0.

For the fourth query, X = (2,1,4,6,3,5) and M = 3. (2,4,6,3,5) achieves the minimum length 5 with score 3.

Sample Input 2

12 8
8 3 5 7 9 6 11 1 10 4 12 2
3 4
10 11
5 8
3 8
4 10
2 10
5 7
1 8

Sample Output 2

2
2
2
4
5
7
2
5