[R8E]区间MEX - 代码源竞赛平台

时空限制

2S/512M

题目描述

区间最小排除数 $\text {MEX}(L,R)$ 指的是没有在区间 $[L,R]$ 中出现过的最小非负整数。

给定一个 $0\sim n$ 的排列 $P$，对 $i=0\sim n$ 分别求 $P$ 有多少个区间 $[L,R]$ 满足 $\text{MEX}(L,R)=i$。

格式

输入格式

第一行包含一个整数 $n$，含义与题目描述相同。

第二行包含 $n+1$ 个整数 $P_i$，表示一个 $0\sim n$ 的排列。

输出格式

输出 $n+1$ 个整数，分别表示对 $i=0\sim n$，满足 $\text{MEX}(L,R)=i$ 的区间 $[L,R]$ 的数量。

样例

样例输入 #1

3
1 0 3 2

样例输出 #1

4 3 2 0

样例解释 #1

$\text{MEX}(1,1)=0$，$\text{MEX}(1,2)=2$，$\text{MEX}(1,3)=2$，$\text{MEX}(1,4)=4$；

$\text{MEX}(2,2)=1$，$\text{MEX}(2,3)=1$，$\text{MEX}(2,4)=1$；

$\text{MEX}(3,3)=0$，$\text{MEX}(3,4)=0$；

$\text{MEX}(4,4)=0$。

数据规模

对于 $20\%$ 的数据，$n\leq 100$。

对于 $60\%$ 的数据，$n\leq 10^4$。

对于 $100\%$ 的数据，$1\leq n\leq 2\times 10^6$，$0\leq P_i\leq n$。数据保证 $P_i$ 是 $0\sim n$ 的一个排列。