昨年出題した Marx Mex を覚えていますか？

数列 $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$ に含まれない最小の非負整数を表します。

入力

1行目に正整数 $n$ が与えられます。

続く1行に $n$ 個の非負整数 $a_1, \dots, a_n$ が与えられます。

続く1行に正整数 $q$ が与えられます。

続く $q$ 行の各行に、クエリを表す正整数 $k$ が与えられます。

出力

$q$ 行にわたって、入力された各 $k$ に対する $f(k)$ を順に出力してください。

入出力例

入力 1

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

出力 1

3
3
1
0
0
0

制約

すべてのデータセットにおいて、$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$ では、特別な制約はありません。