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

$$f(k) = \max_{r-l+1=k} \operatorname*{mex}_{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
2 1 1 0 0 3
6
1
2
3
4
5
6

Output 1

1
2
2
3
3
4

Subtasks

For $100\%$ of the data, it is guaranteed that $1\leq q\leq n\leq 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 5$, it is guaranteed that $q\leq 10$.

For test cases $6\sim 7$, it is guaranteed that $a_i\leq 10$.

For test cases $8\sim 10$, there are no additional restrictions.