Paw-Sealed Patrols

Time limit: 2000 msMemory limit: 256 MB

Gats the cat has a toy string with $N$ knots arranged in a row. The $i$ -th knot has color $C_i$ .

Gats may inspect any segment $[L,R]$ , where $1 \le L \le R \le N$ . The segment is paw-sealed when both of the following conditions hold:

Among $C_L, C_{L+1}, \ldots, C_R$ , the color occurs at exactly one position.

When $L=R$ , the single knot satisfies both conditions.

The variety of a segment is the number of distinct colors appearing in it. Let $D$ be the number of distinct colors in the entire toy string. For every $K$ satisfying $1 \le K \le D$ , count the paw-sealed segments with variety exactly $K$ .

Input

The first line contains an integer $N$ ( $1 \le N \le 2 \times 10^5$ ), the number of knots.

The second line contains $N$ integers (), representing the knot colors.

Output

Let $D$ be the number of distinct colors among all knots. Print $D$ integers on one line. The $K$ -th integer, for $1 \le K \le D$ , must equal the number of paw-sealed segments whose variety is exactly $K$ .

Samples

Sample 1

Input

5
1 2 1 3 2

Output

5 4 2

There are $5$ , $4$ , and $2$ paw-sealed segments of varieties $1$ , $2$ , and $3$ , respectively. The two segments of variety are and .

Paw-Sealed Patrols

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2