You will be given a long array . The length of the array is where will be given. The first elements of the array will be given as input. The rest of the elements will be calculated as where .
Let's say for , the first elements are , then the rest of the elements of the array will be and so on.
You will also be given queries. In each query, you will be given a number . You need to print the next smaller element after position . In other words, you need to find a number where and is the smallest possible. If there is no such number exists, print .
The first line of input will have two integers and .
In the next line, the first elements of the array will be given where for every .
Each of the following lines will have one integer .
For each query, print the desired number as described in the problem statement.
Input | Output |
---|---|
3 5 3 6 1 1 2 3 4 5 | 1 1 -1 2 2 |