Find the Next!

★★★★★

3.7

11 votes

Algorithms, Arrays, Binary tree, Easy, Hash Maps, Implementation, One-dimensional, Quick Sort, Sorting

Details

Submissions

Discussion

Editorial

Problem

You are given an array A of length N. For any given integer X, you need to find an integer Z strictly greater than X such that Z is not present in the array A. You need to minimise the value of Z.

Input format :

First line : Two space seperated integers N and Q denoting the number of elements in array A and the number of queries respectively
Second line : N space seperated integers denoting the array elements
Next Q lines : Each line consists of an integer X

Output fomat :

Print Q lines, each line denoting the answer to the corresponding query.

Constraints :

$1 \le N,Q \le 10^{5}$
$1 \le A_{i},X \le 10^{9}$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For the first query, the minimum element greater than 3 and not present in the given array is 4. Similarly, for the second query, the answer is 10.