P9785 [ROIR 2020] Fighting the Routine (Day1)

**Translated from [ROIR 2020](http://neerc.ifmo.ru/school/archive/2019-2020.html) Day1 T3.** ***[Борьба с рутиной ](http://neerc.ifmo.ru/school/archive/2019-2020/ru-olymp-regional-2020-day1.pdf), 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}$.

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 $n$ numbers, which are $S_{1\sim n}$.

#### Sample 1 Explanation - $S_1$: | Segment | All task types | Number of distinct task types | | :----: | :------------: | :---------------------------: | | $1-1$ | $1$ | $1$ | | $2-2$ | $3$ | $1$ | | $3-3$ | $2$ | $1$ | | $4-4$ | $1$ | $1$ | | $5-5$ | $2$ | $1$ | So $S_1=1+1+1+1+1=5$. - $S_2$: | Segment | All task types | Number of distinct task types | | :----: | :------------: | :---------------------------: | | $1-2$ | $1,3$ | $2$ | | $2-3$ | $3,2$ | $2$ | | $3-4$ | $2,1$ | $2$ | | $4-5$ | $1,2$ | $2$ | So $S_2=2+2+2+2=8$. - $S_3$: | Segment | All task types | Number of distinct task types | | :----: | :------------: | :---------------------------: | | $1-3$ | $1,3,2$ | $3$ | | $2-4$ | $3,2,1$ | $3$ | | $3-5$ | $2,1,2$ | $2$ | So $S_3=3+3+2=8$. - $S_4$: | Segment | All task types | Number of distinct task types | | :----: | :------------: | :---------------------------: | | $1-4$ | $1,3,2,1$ | $3$ | | $2-5$ | $3,2,1,2$ | $3$ | So $S_4=3+3=6$. - $S_5$: | Segment | All task types | Number of distinct task types | | :----: | :------------: | :---------------------------: | | $1-5$ | $1,3,2,1,2$ | $3$ | 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$. | Subtask ID | Special Constraints | Score | | :--------: | :-----------------: | :---: | | $1$ | $1\leq n \leq 50, 1 \leq a_i \leq 50$ | $12$ | | $2$ | $1\leq n \leq 50, 1 \leq a_i \leq 10^9$ | $10$ | | $3$ | $1\leq n \leq 500, 1 \leq a_i \leq 10^9$ | $10$ | | $4$ | $1\leq n \leq 5000, 1 \leq a_i \leq 5000$ | $12$ | | $5$ | $1\leq n \leq 5000, 1 \leq a_i \leq 10^9$ | $10$ | | $6$ | $1\leq n \leq 2\times 10^5, 1 \leq a_i \leq 50$ | $16$ | | $7$ | No special constraints | $30$ | Translated by ChatGPT 5