分数: 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