Дан массив $a_1, a_2, \dots, a_n$. Для каждого $k$ найдите значение

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

Здесь $\operatorname{mex} S$ обозначает минимальное неотрицательное целое число, не входящее в множество $S$.

Входные данные

В первой строке введено целое положительное число $n$.

В следующей строке введено $n$ неотрицательных целых чисел $a_1, \dots, a_n$.

В следующей строке введено целое положительное число $q$.

В следующих $q$ строках введено по одному целому положительному числу $k$, соответствующему запросу.

Выходные данные

Выведите $q$ строк, содержащих ответы на запросы $f(k)$ в порядке их поступления.

Примеры

Пример 1

Входные данные

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

Выходные данные

1
2
2
3
3
4

Подзадачи

Для $100\%$ данных гарантируется, что $1\leq q\leq n\leq 10^5$, $0\leq a_i\leq n$, и все значения $k$ в запросах различны.

Для тестов $1\sim 3$ гарантируется $n\leq 100$.

Для тестов $4\sim 5$ гарантируется $q\leq 10$.

Для тестов $6\sim 7$ гарантируется $a_i\leq 10$.

Для тестов $8\sim 10$ дополнительных ограничений нет.