Do you remember the MaxMex problem we set last year?

Given a sequence $a_1, a_2, \dots, a_n$, for each $k$, please answer:

$$f(k) = \operatorname*{mex}_{r-l+1=k} \max_{i=l}^r a_i. $$

Where $\operatorname{mex} S$ denotes the smallest non-negative integer not present in $S$.

Input

The first line contains a positive integer $n$.

The next line contains $n$ non-negative integers $a_1, \dots, a_n$.

The next line contains a positive integer $q$.

The next $q$ lines each contain a positive integer $k$, representing a query.

Output

Output $q$ lines, answering $f(k)$ for each input $k$ in order.

Examples

Input 1

6
1 1 2 0 0 0
6
1
2
3
4
5
6

Output 1

3
3
1
0
0
0

Subtasks

For $100\%$ of the data, it is guaranteed that $1\leq q\leq n\leq 2\times 10^5$, $0\leq a_i\leq n$, and all queried $k$ are distinct.

For test cases $1\sim 3$, it is guaranteed that $n\leq 100$.

For test cases $4\sim 6$, it is guaranteed that $q\leq 10$.

For test cases $7\sim 10$, there are no special restrictions.