题目描述

给定一个数列 $a_1, a_2, \ldots, a_n$ ，对于 $k$ ，请你回答 $f(k)=\max _{r-l+1=k} \operatorname{mex}_{i=l}^r a_i$.

其中 $\operatorname{mex} S$ 表示 $S$ 中未出现的最小非负整数。

$f(k)$ 求解的是数列中长度为 $k$ 的子串中未出现的最小非负整数的最大值。

输入格式

第一行输入一个正整数 $n$ 。 接下来一行输入 $n$ 个非负整数 $a_1, \ldots, a_n$ 。 接下来一行输入一个正整数 $q$ 。 接下来 $q$ 行每行输入一个正整数 $k$ ，表示一个询问。

输出格式

输出 $q$ 行，按顺序回答输入的 $k$ 对应的 $f(k)$ 。

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$ 互不相同。

• Subtask 1 (30 pts) : 保证 $n \leq 100$ 。
• Subtask 2 (20 pts) : 保证 $q \leq 10$ 。
• Subtask 3 (20 pts) : 保证 $a_i \leq 10$ 。
• Subtask 4 (30 pts)：无特殊限制。

大样例

大样例下载