Distinct Job Types Sum

This problem was translated from ROIR 2020 Day1 T3. In this task, we evaluate an employee’s performance based on the variety of daily tasks completed over a period of n consecutive days.

On day i, the employee performs a job identified by an integer a_i. For any integer d (where 1 ≤ d ≤ n), consider all contiguous segments of d days. For each such segment, let the contribution be the number of distinct jobs performed in that segment. Denote by S_d the sum of these contributions over all contiguous segments of length d.

Your task is to compute and output the values of \[ S_1, S_2, \dots, S_n \] for the given sequence.

Note: All formulas are represented in LaTeX format.

inputFormat

The first line contains a single integer n (1 ≤ n).

The second line contains n integers a₁, a₂, \dots, a_n representing the jobs performed on each day.

outputFormat

Output a single line containing n space‐separated integers: S₁, S₂, \dots, S_n.

sample

3
1 2 3

3 4 3