【题目描述】 有一排 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。