D - Forbidden List 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

相異なる N 個の整数からなるリストがあります。リストの i 個目 (1 \leq i \leq N) の整数は A_i です。

Q 個の質問が与えられるので、それぞれの答えを求めてください。j 個目の質問 (1 \leq j \leq Q) は以下の通りです。

  • X_j 以上の整数であってリストに含まれないもののうち、小さいほうから Y_j 番目の値を求めよ。

制約

  • 1 \leq N \leq 3 \times 10^5
  • 1 \leq Q \leq 3 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • A_1, \dots, A_N は相異なる
  • 1 \leq X_j \leq 10^9 (1 \leq j \leq Q)
  • 1 \leq Y_j \leq 10^9 (1 \leq j \leq Q)
  • 入力される値はすべて整数

入力

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

N Q
A_1 \cdots A_N
X_1 Y_1
\vdots
X_Q Y_Q

出力

Q 行出力せよ。j 行目 (1 \leq j \leq Q) には j 個目の質問の答えを出力せよ。

入力例 1

5 4
16 9 2 3 1
6 10
12 4
1 1
1000000000 1000000000

出力例 1

17
15
4
1999999999

1 個目の質問について、6 以上の整数であってリストに含まれないもののうち、小さいほうから 10 個を挙げると 6,\ 7,\ 8,\ 10,\ 11,\ 12,\ 13,\ 14,\ 15,\ 17 となります。したがって、質問の答えは 17 です。

2 個目の質問について、12 以上の整数であってリストに含まれないもののうち、小さいほうから 4 個を挙げると 12,\ 13,\ 14,\ 15 となります。したがって、質問の答えは 15 です。

3 個目の質問について、1 以上の整数であってリストに含まれないもののうち、小さいほうから 1 番目の値は 4 です。

4 個目の質問について、1\,000\,000\,000 以上の整数であってリストに含まれないもののうち、小さいほうから 1\,000\,000\,000 番目の値は 1\,999\,999\,999 です。

入力例 2

10 10
284008711 658403910 982178205 50598815 694147827 230009803 763277509 509451676 821970166 284008710
740250292 159734720
255870361 8400028
23659634 718117163
697334729 301140741
698853172 270344164
713418715 285312509
50065000 52368934
46642556 591869945
607623561 273664826
482426028 265015448

出力例 2

899985013
264270388
741776803
998475472
969197337
998731226
102433934
638512505
881288390
747441478

Score : 400 points

Problem Statement

There is a list consisting of N distinct integers. The i-th (1 \leq i \leq N) integer in the list is A_i.

You are given Q questions; answer each of them. The j-th question (1 \leq j \leq Q) is as follows:

  • Find the Y_j-th smallest value among the integers greater than or equal to X_j that are not in the list.

Constraints

  • 1 \leq N \leq 3 \times 10^5
  • 1 \leq Q \leq 3 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • A_1, \dots, A_N are distinct.
  • 1 \leq X_j \leq 10^9 (1 \leq j \leq Q)
  • 1 \leq Y_j \leq 10^9 (1 \leq j \leq Q)
  • All input values are integers.

Input

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

N Q
A_1 \cdots A_N
X_1 Y_1
\vdots
X_Q Y_Q

Output

Output Q lines. The j-th line (1 \leq j \leq Q) should contain the answer to the j-th question.

Sample Input 1

5 4
16 9 2 3 1
6 10
12 4
1 1
1000000000 1000000000

Sample Output 1

17
15
4
1999999999

For the first question, the smallest 10 integers greater than or equal to 6 that are not in the list are 6,\ 7,\ 8,\ 10,\ 11,\ 12,\ 13,\ 14,\ 15,\ 17. Thus, the answer to the question is 17.

For the second question, the smallest 4 integers greater than or equal to 12 that are not in the list are 12,\ 13,\ 14,\ 15. Thus, the answer to the question is 15.

For the third question, the 1st smallest value among the integers greater than or equal to 1 that are not in the list is 4.

For the fourth question, the 1\,000\,000\,000-th smallest value among the integers greater than or equal to 1\,000\,000\,000 that are not in the list is 1\,999\,999\,999.

Sample Input 2

10 10
284008711 658403910 982178205 50598815 694147827 230009803 763277509 509451676 821970166 284008710
740250292 159734720
255870361 8400028
23659634 718117163
697334729 301140741
698853172 270344164
713418715 285312509
50065000 52368934
46642556 591869945
607623561 273664826
482426028 265015448

Sample Output 2

899985013
264270388
741776803
998475472
969197337
998731226
102433934
638512505
881288390
747441478