Pamiętasz, jak w zeszłym roku przygotowaliśmy zadanie 马克思么克斯?

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

$$f(k) = \operatorname*{mex}_{r-l+1=k} \max_{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ę jedna 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ę jedna liczba całkowita dodatnia $q$.

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

Wyjście

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

Przykład

Wejście 1

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

Wyjście 1

3
3
1
0
0
0

Podzadania

Dla $100\%$ danych wejściowych zachodzi $1\leq q\leq n\leq 2\times 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 6$ zachodzi $q\leq 10$.

Dla testów $7\sim 10$ nie ma dodatkowych ograniczeń.