Помните, в прошлом году мы предлагали задачу Макс-мекс?

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

3
3
1
0
0
0

Подзадачи

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

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

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

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