← 返回题目列表

AtCoder · abc440_d

D. 禁止名单 2

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有一个列表,其中包括 N 不同的整数。的 i-th (1 \leq i \leq N) 列表中的整数是 A_i.

你被给予 Q 问题;回答他们每个人。的 j第一个问题(1 \leq j \leq Q)如下:

  • 找到 Y_j- 大于或等于的整数中的第一个最小值 X_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

对于第一个问题,最小的 10 大于或等于的整数 6 不在列表中的是 6,\ 7,\ 8,\ 10,\ 11,\ 12,\ 13,\ 14,\ 15,\ 17。因此,问题的答案是 17.

对于第二个问题,最小的 4 大于或等于的整数 12 不在列表中的是 12,\ 13,\ 14,\ 15。因此,问题的答案是 15.

对于第三个问题, 1大于或等于的整数中的第一个最小值 不在列表中的 1 是 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