F - Prefix LIS Query Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。

Q 個のクエリを処理してください。 i\ (1\leq i\leq Q) 番目のクエリは以下の通りです：

  • 整数 R_i,X_i が与えられる。数列 (A_1,A_2,\dots,A_{R_i}) の（連続とは限らない）部分列であって、狭義単調増加であり、かつ全ての要素が X_i 以下であるようなものの長さの最大値を求めよ。 なお、X_i \geq \min\lbrace A_1, A_2,\dots,A_{R_i} \rbrace が保証される。

制約

  • 1\leq N,Q \leq 2\times 10^5
  • 1\leq A_i \leq 10^9
  • 1\leq R_i\leq N
  • \min\lbrace A_1, A_2,\dots,A_{R_i} \rbrace\leq X_i\leq 10^9
  • 入力は全て整数

入力

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

N Q
A_1 A_2 \dots A_N
R_1 X_1
R_2 X_2
\vdots
R_Q X_Q

出力

Q 行出力せよ。 i\ (1\leq i \leq Q) 行目には、i 番目のクエリに対する答えを出力せよ。

入力例 1

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

出力例 1

2
1
2
  • 1 番目のクエリ：数列 (2,4) の狭義単調増加な部分列であって、全ての要素が 5 以下であるようなものの長さの最大値は 2 です。
    具体的には、部分列 (2,4) が該当します。
  • 2 番目のクエリ：数列 (2,4,1,3,3) の狭義単調増加な部分列であって、全ての要素が 2 以下であるようなものの長さの最大値は 1 です。
    具体的には、部分列 (2) および (1) が該当します。
  • 3 番目のクエリ：数列 (2,4,1,3,3) の狭義単調増加な部分列であって、全ての要素が 3 以下であるようなものの長さの最大値は 2 です。
    具体的には、部分列 (2,3) および (1,3) が該当します。

入力例 2

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

出力例 2

4
1
1
2
1
5
3
4

Score : 500 points

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N.

Answer Q queries. The i-th query (1 \leq i \leq Q) is as follows:

  • You are given integers R_i and X_i. Consider a subsequence (not necessarily contiguous) of (A_1, A_2, \dots, A_{R_i}) that is strictly increasing and consists only of elements at most X_i. Find the maximum possible length of such a subsequence. It is guaranteed that X_i \geq \min\lbrace A_1, A_2,\dots,A_{R_i} \rbrace.

Constraints

  • 1 \leq N,Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq R_i \leq N
  • \min\lbrace A_1, A_2,\dots,A_{R_i} \rbrace\leq X_i\leq 10^9
  • All input values are integers.

Input

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

N Q
A_1 A_2 \dots A_N
R_1 X_1
R_2 X_2
\vdots
R_Q X_Q

Output

Print Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

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

Sample Output 1

2
1
2
  • 1st query: For the sequence (2,4), the longest strictly increasing subsequence with all elements at most 5 has length 2.
    Specifically, (2,4) qualifies.
  • 2nd query: For the sequence (2,4,1,3,3), the longest strictly increasing subsequence with all elements at most 2 has length 1.
    Specifically, (2) and (1) qualify.
  • 3rd query: For the sequence (2,4,1,3,3), the longest strictly increasing subsequence with all elements at most 3 has length 2.
    Specifically, (2,3) and (1,3) qualify.

Sample Input 2

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

Sample Output 2

4
1
1
2
1
5
3
4