Dany jest ciąg $a_1, a_2, \dots, a_n$. Dla każdego $k$ oblicz:

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

Gdzie $\operatorname{mex} S$ oznacza najmniejszą nieujemną liczbę całkowitą, która nie występuje w zbiorze $S$.

Wejście

W pierwszej linii znajduje się liczba całkowita dodatnia $n$.

W drugiej linii znajduje się $n$ nieujemnych liczb całkowitych $a_1, \dots, a_n$.

W trzeciej linii znajduje się liczba całkowita dodatnia $q$.

W kolejnych $q$ liniach znajduje się po jednej liczbie całkowitej dodatniej $k$, reprezentującej zapytanie.

Wyjście

Wypisz $q$ linii, odpowiadając na zapytania o $f(k)$ w kolejności ich występowania na wejściu.

Przykład

Przykład 1

Wejście

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

Wyjście

1
2
2
3
3
4

Podzadania

Dla $100\%$ danych wejściowych zachodzi $1\leq q\leq n\leq 10^5$ oraz $0\leq a_i\leq n$. Wartości $k$ w zapytaniach są parami różne.

Dla testów $1\sim 3$ zachodzi $n\leq 100$.

Dla testów $4\sim 5$ zachodzi $q\leq 10$.

Dla testów $6\sim 7$ zachodzi $a_i\leq 10$.

Dla testów $8\sim 10$ brak dodatkowych ograniczeń.