Next Smaller Element

emrul_mu Replay of Ada Lovelace Na...
Limits 1s, 512 MB

You will be given a long array arar. The length of the array is n100n^{100} where nn will be given. The first nn elements ar[1],ar[2],...,ar[n]ar[1],ar[2],...,ar[n] of the array will be given as input. The rest of the elements will be calculated as ar[i]=ar[((i1)modn)+1]+((i1)/n)ar[i] = ar[((i - 1)\mod n) + 1] + ((i - 1) / n) where n<in100n < i \le n^{100}.

Let's say for n=3n = 3, the first nn elements are [3,6,1][3, 6, 1], then the rest of the elements of the array will be [4,7,2,5,8,3,6,9,4][4, 7, 2, 5, 8, 3, 6, 9, 4] and so on.

You will also be given qq queries. In each query, you will be given a number xx. You need to print the next smaller element after position xx. In other words, you need to find a number ar[j]ar[j] where ar[j]<ar[x] and j>xar[j] < ar[x] \text{ and } j > x and jj is the smallest possible. If there is no such number exists, print 1-1.

Input

The first line of input will have two integers n (2n3×105)n\text{ } (2 ≤ n ≤ 3\times 10^{5}) and q (1q105)q\text{ }(1 \le q \le 10^5).

In the next line, the first nn elements of the array will be given where 1ar[i]3×1051 ≤ ar[i] ≤ 3 \times 10^5 for every 1in1 ≤ i ≤ n.

Each of the following qq lines will have one integer x (1x1012)x\text{ }(1 \le x \le 10^{12}).

Output

For each query, print the desired number as described in the problem statement.

Sample

InputOutput
3 5
3 6 1
1
2
3
4
5
1
1
-1
2
2

Submit

Login to submit.

Statistics

78% Solution Ratio
BrehamPieEarliest, 2M ago
steinumFastest, 0.0s
steinumLightest, 6.0 kB
steinumShortest, 648B
Toph uses cookies. By continuing you agree to our Cookie Policy.