Forbidden List 2

AtCoder

IDabc440_d

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

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

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 $1$st 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$.

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

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Forbidden List 2",
    "description": {
      "content": "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 \\le",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc440_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is a list consisting of $N$ distinct integers. The $i$\\-th ($1 \\leq i \\leq N$) integer in the list is $A_i$.\nYou are given $Q$ questions; answer each of them. The $j$\\-th question ($1 \\leq j \\le...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments