Problem Description

Translated from ROIR 2020 Day1 T3. Борьба с рутиной , translator: ShineEternal.

An important factor in evaluating an employee's performance is the ability to handle routine tasks.

We consider an employee's work over consecutive $n$ days. The task performed on day $i$ is $a_i$.

To evaluate the employee's performance, we use the following method:

Choose an integer $d$ and consider all consecutive segments of $d$ days. For each such segment, count the number of different types of tasks the employee completed.

Let $S_d$ be the sum, over all such consecutive $d$-day segments, of the number of distinct task types completed in that segment.

Now you need to compute $S_{1\sim n}$.

Input Format

The input consists of two lines.

The first line contains an integer $n$, representing the total number of working days.

The second line contains $n$ integers, representing the task type ID done each day.

Output Format

Output $n$ numbers, which are $S_{1\sim n}$.

5
1 3 2 1 2

5 8 8 6 3

3
10 10 10

3 2 1

Hint

Sample 1 Explanation

• $S_1$:

So $S_1=1+1+1+1+1=5$.

• $S_2$:

So $S_2=2+2+2+2=8$.

• $S_3$:

So $S_3=3+3+2=8$.

• $S_4$:

So $S_4=3+3=6$.

• $S_5$:

So $S_5=3$.

Constraints

For $100\%$ of the testdata, $1\leq n\leq 2\times 10^5$, $1\leq a_i\leq 10^9$.

Translated by ChatGPT 5