题目描述

给定正整数 $n$。下面称长度为 $n$、每项元素均属于 $[1,n]\cap\mathbb Z$ 的序列为一个好序列。

对于一个好序列 $a=(a_1,a_2,\ldots,a_n)$，定义 $f(a)$ 如下：

• 将 $a$ 视作一张有 $n$ 个点、每个点恰好有一条出边的有向图，点 $i$ 的出边指向点 $a_i$；
• 有 $n$ 个人，编号为 $1,2,\ldots,n$；在时刻 $0$，编号为 $u$ 的人站在点 $u$；
• 对于时刻 $t$ 站在点 $u$ 上的人，其在时刻 $t+1$ 走到点 $a_u$；
• 记编号为 $u$ 的人在时刻 $t$ 所处的点为 $idx_{u,t}$；
• 定义

$$f(a)=\max_{\substack{t\ge 0\\1\le u\le n}} \sum_{i=1}^{n}[idx_{i,t}=u],$$

其中 $[P]$ 表示命题 $P$ 成立时取 $1$，否则取 $0$。

给定一个好序列 $b$。对于每个 $0\le k\le n$，考虑所有能够从 $b$ 出发、修改至多 $k$ 个元素后得到的好序列 $b'$，求 $f(b')$ 的最大值。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $b_1,b_2,\ldots,b_n$。

输出格式

输出一行 $n+1$ 个整数，依次表示 $k=0,1,\ldots,n$ 时的答案。

样例

样例 1

输入

10
1 1 10 1 5 6 5 8 8 1

输出

5 7 9 10 10 10 10 10 10 10 10

数据范围

$$1\le n\le 10^5,\qquad 1\le b_i\le n.$$

子任务

子任务编号	$n\le$	特殊性质	分值
1	$10$	无	10
2	$3000$		40
3	$10^5$	A	10
4		B
5		无	30

特殊性质：

• A： 所有 $b_i$ 均在 $[1,n]$ 内独立均匀随机生成；
• B： 序列 $b$ 中至多有 $100$ 种不同的元素。