还记得去年我们出了个 马克思么克斯 吗？

题目描述

给定一个数列 $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$ 行，按顺序回答输入的 $k$ 对应的 $f(k)$。

样例数据

样例输入

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

样例输出

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$，无特殊限制。