← 返回题目列表

Codeforces · 643/A

A. 熊和颜色

中文机器翻译题面 查看原题

Bear Limak 有 n 个彩色球,排成一长排。球从左到右编号为 1 到 n。有 n 种可能的颜色,也编号为 1 到 n。第 i 个球的颜色为 ti。

对于球的固定间隔(连续元素的集合),我们可以定义主颜色。它是间隔中出现次数最多的颜色。如果某些颜色之间出现平局,则选择数字(索引)最小的颜色作为主导颜色。

总共有 $$\frac{n(n+1)}{2}$$ 个非空区间。对于每种颜色,您的任务是计算该颜色占主导地位的间隔数。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 5000) — 球的数量。

第二行包含 n 个整数 t1, t2, ..., tn (1 ≤ ti ≤ n),其中 ti 是第 i 个球的颜色。

输出

打印 n 个整数。其中第 i 个应该等于 i 为主色的间隔数。

示例

输入 #1

4
1 2 1 2

输出 #1

7 3 0 0

输入 #2

3
1 1 1

输出 #2

6 0 0

注意

在第一个示例中,颜色 2 在三个间隔中占主导地位:

- 区间 [2, 2] 包含一个球。该球的颜色为 2,因此它显然是主色。
- 区间 [4, 4] 包含一个球,颜色又为 2。
- 区间 [2, 4] 包含两个颜色 2 的球和一个颜色 1 的球。

还有 7 个间隔,颜色 1 在所有间隔中占主导地位。