[THUPC 2024 初赛] 套娃
题目描述
我们定义一个集合的 $\operatorname{mex}$ 是最小的不在 $S$ 中的非负整数。
给定一个序列 $a_1,\dots,a_n$,对于每个 $1\leq k\leq n$,我们按照如下方式定义 $b_k$:
- 对于 $a$ 的所有长为 $k$ 的子区间,求出这个子区间构成的数集的 $\operatorname{mex}$。
- 对于求出的所有 $\operatorname{mex}$,求出这个数集自己的 $\operatorname{mex}$,记为 $b_k$。
请你求出序列 $b$。
输入输出格式
输入格式
第一行输入一个正整数 $n$($1\leq n\leq 10^5$)。
第二行输入 $n$ 个整数 $a_1,\dots,a_n$($0\leq a_i\leq n$)。
输出格式
一行输出 $n$ 个整数 $b_1,\dots,b_n$。
输入输出样例
输入样例 #1
6
0 0 0 1 2 3
输出样例 #1
2 3 4 0 0 0
说明
### 题目使用协议
来自 THUPC2024(2024年清华大学学生程序设计竞赛暨高校邀请赛)初赛。
以下『本仓库』皆指 THUPC2024 初赛 官方仓库([https://github.com/ckw20/thupc2024_pre_public](https://github.com/ckw20/thupc2024_pre_public))
1. 任何单位或个人都可以免费使用或转载本仓库的题目;
2. 任何单位或个人在使用本仓库题目时,应做到无偿、公开,严禁使用这些题目盈利或给这些题目添加特殊权限;
3. 如果条件允许,请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法;否则,请附上本仓库的 github 地址。