时间限制： 3.0 秒

空间限制： 256 MB

题目描述

SAM 有 $n$ 个有颜色的球，被排成一列，它们分别被从左到右标号为 $1$ 到 $n$。它们中共有 $n$ 种颜色，也被标号为 $1$ 到 $n$。第 $i$ 个球的颜色为 $c_{i}$。

对于一个连续下标区间的球，SAM 定义了它的主色调。主色调就是区间中出现次数最多的颜色，如果有多种颜色出现最多的次数，那颜色标号最小的颜色是主色调。

总共有 $\frac{n \cdot (n+1)}{2}$ 个非空区间。对于每种颜色，SAM 想要知道它是多少个区间的主色调。

输入格式

从标准输入读入数据。

本题为不定组输入，以文件 EOF 为结尾，保证数据组数不超过 $20$。

每组输入第一行为 $n~(1 \leq n \leq 5000)$ 表示球和颜色的个数。

第二行含有 $n$ 个整数 $c_{1} , c_{2} , \ldots , c_{n}~(1\le c_i\le n)$，其中 $c_{i}$ 是第 $i$ 个球的颜色。

输出格式

输出到标准输出。

每组输出一行 $n$ 个整数，用空格分开，行末没有空格，第 $i$ 个数等于 $i$ 是主色调的区间的个数。

4
1 2 1 2
3
1 1 1

7 3 0 0
6 0 0