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

入力

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

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

3行目に正整数 $q$ が与えられます。

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

出力

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

入出力例

入力 1

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

出力 1

1
2
2
3
3
4

小課題

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