Logo Universal Online Judge

UOJ

时间限制:2 s 空间限制:512 MB
Statistics

【题目描述】 有一排 n 个弹药包,从 1 到 n 编号。第 i 个弹药包有颜色 ci。

黎明卿有 k 个祈手,他们将弹药包分成 k 段,每一段是一个连续的区间,每个弹药包都属于且仅属于一个段,每个祈手取一段。

一个祈手的战斗力为他所拥有的弹药包颜色数,请你最大化所有祈手的战斗力之和。

由于黎明卿不知道来了几个祈手,所以他需要你帮他求出 k = 1, 2, 3, . . . , n 的答案。

【输入格式】

从标准输入读入数据。

第一行一个数 n。

第二行 n 个数 c1, c2, . . . , cn。

【输出格式】

输出到标准输出。

一行 n 个数,第 i 个数为 k = i 的答案。

【样例 1 输入】

10
1 2 3 1 2 3 1 2 3 1

【样例 1 输出】

3 6 9 10 10 10 10 10 10 10

【样例 2 输入】

20
1 1 2 3 2 2 5 1 1 4 5 2 5 4 3 4 2 4 3 3

【样例 2 输出】

5 9 12 14 16 17 18 19 20 20 20 20 20 20 20 20 20 20 20 20

下发文件

【子任务】

对于全部数据,1 ≤ n ≤ 10^5,1 ≤ ci ≤ n。