Fighting Routine

Time limit2sMemory limit512 MB

Summary

For every window length d from 1 to n, sum the number of distinct task types over all length-d windows of the given array.

Level: Medium7 of 10
Topics: Array, Prefix sum, Combinatorics, Math
Solved: No attempts yet

Problem

Fighting routine is an important part of improving employee productivity. Let us build a mathematical model of the diversity of task types an employee performs at a company.

Consider an employee working over $n$ consecutive working days. Every day the employee performs exactly one type of task; let the type of task performed on day $i$ be an integer $a_i$ .

To measure how routine the employee's work is, we use the following quantity. Fix an integer $d$ and consider all segments of $d$ consecutive working days. For each such segment, count the number of distinct task types the employee performed over those days, then sum these counts. Call the resulting value $S_d$ , the $d$ -diversity. The higher the $d$ -diversity, the more distinct task types the employee performed. The variability profile of the employee is the array $[S_1, S_2, \ldots, S_n]$ .

Write a program that, given the sequence $a_1, a_2, \ldots, a_n$ of task types the employee performs, computes the variability profile of that employee.

Input

The first line contains a single integer $n$ , the number of consecutive working days to analyze ( $1 \le n \le 2 \cdot 10^5$ ).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ , the task types the employee performed ( $1 \le a_i \le 10^9$ ).

Output

Print $n$ integers: $S_1, S_2, \ldots, S_n$ .

Hint

Consider how the values $S_d$ are computed in the first sample.

1-diversity: sum the number of distinct task types the employee performed over all segments consisting of one day.

Days	Task types	Distinct count
1 - 1	1	1
2 - 2	3	1
3 - 3	2	1
4 - 4	1	1
5 - 5	2	1

The 1-diversity value is $S_1 = 1 + 1 + 1 + 1 + 1 = 5$ .

2-diversity: sum the number of distinct task types the employee performed over all segments consisting of two days.

Days	Task types	Distinct count
1 - 2	1, 3	2
2 - 3	3, 2	2
3 - 4	2, 1	2
4 - 5	1, 2	2

The 2-diversity value is $S_2 = 2 + 2 + 2 + 2 = 8$ .

3-diversity: sum the number of distinct task types the employee performed over all segments consisting of three days.

Days	Task types	Distinct count
1 - 3	1, 3, 2	3
2 - 4	3, 2, 1	3
3 - 5	2, 1, 2	2

The 3-diversity value is $S_3 = 3 + 3 + 2 = 8$ .

4-diversity: sum the number of distinct task types the employee performed over all segments consisting of four days.

Days	Task types	Distinct count
1 - 4	1, 3, 2, 1	3
2 - 5	3, 2, 1, 2	3

The 4-diversity value is $S_4 = 3 + 3 = 6$ .

5-diversity: sum the number of distinct task types the employee performed over all segments consisting of five days.

Days	Task types	Distinct count
1 - 5	1, 3, 2, 1, 2	3

The 5-diversity value is $S_5 = 3$ .

Examples2

Example 1
Input
```
5
1 3 2 1 2
```
Expected output
```
5 8 8 6 3
```
Example 2
Input
```
3
10 10 10
```
Expected output
```
3 2 1
```