A10325 | Bear and Colors

Bear Limak has $n$ colored balls, arranged in one long row. Balls are numbered $1$ through $n$ , from left to right. There are $n$ possible colors, also numbered $1$ through $n$ . The $i$ -th ball has color $t_{i}$ .

For a fixed interval (set of consecutive elements) of balls we can define a dominant color. It's a color occurring the biggest number of times in the interval. In case of a tie between some colors, the one with the smallest number (index) is chosen as dominant.

There are  non-empty intervals in total. For each color, your task is to count the number of intervals in which this color is dominant.

The first line of the input contains a single integer $n$ ( $1<=n<=5000$ ) — the number of balls.

The second line contains $n$ integers $t_{1},t_{2},...,t_{n}$ ( $1<=t_{i}<=n$ ) where $t_{i}$ is the color of the $i$ -th ball.

Print $n$ integers. The $i$ -th of them should be equal to the number of intervals where $i$ is a dominant color.