루틴과의 싸움

직원의 업무 효율을 높이는 데 중요한 요소는 루틴과의 싸움이다. 회사에서 직원이 수행하는 작업 유형의 다양성을 수학적으로 모델링해 보자.

직원이 연속된 $n$일 동안 일한다고 하자. 매일 직원은 정확히 한 가지 유형의 작업을 수행하며, $i$번째 날에 수행하는 작업 유형을 정수 $a_i$로 나타내자.

직원 업무의 루틴 정도를 평가하기 위해 다음과 같은 지표를 사용하자. 정수 $d$를 고정하고, 연속한 $d$일로 이루어진 모든 구간을 생각하자. 각 구간마다 직원이 그동안 수행한 서로 다른 작업 유형의 개수를 구해 모두 더하자. 이 값을 $S_d$라 하고 $d$-다양성이라고 부르자. $d$-다양성이 클수록 직원이 더 다양한 유형의 작업을 수행한 것이다. 직원의 변동성 프로필을 값의 배열 $[S_1, S_2, \ldots, S_n]$이라고 하자.

직원이 수행하는 작업 유형의 수열 $a_1, a_2, \ldots, a_n$이 주어질 때, 그 직원의 변동성 프로필을 계산하는 프로그램을 작성하라.

첫째 줄에 분석할 연속된 근무일 수 $n$이 주어진다 ($1 \le n \le 2 \cdot 10^5$).

둘째 줄에 직원이 수행한 작업 유형 $n$개 $a_1, a_2, \ldots, a_n$이 주어진다 ($1 \le a_i \le 10^9$).

$n$개의 정수 $S_1, S_2, \ldots, S_n$을 출력한다.

첫 번째 예제에서 $S_d$가 어떻게 계산되는지 살펴보자.

1-다양성: 하루로 이루어진 모든 구간에서 직원이 수행한 서로 다른 작업 유형의 개수를 모두 더한다.

1-다양성의 값은 $S_1 = 1 + 1 + 1 + 1 + 1 = 5$이다.

2-다양성: 이틀로 이루어진 모든 구간에서 직원이 수행한 서로 다른 작업 유형의 개수를 모두 더한다.

2-다양성의 값은 $S_2 = 2 + 2 + 2 + 2 = 8$이다.

3-다양성: 사흘로 이루어진 모든 구간에서 직원이 수행한 서로 다른 작업 유형의 개수를 모두 더한다.

3-다양성의 값은 $S_3 = 3 + 3 + 2 = 8$이다.

4-다양성: 나흘로 이루어진 모든 구간에서 직원이 수행한 서로 다른 작업 유형의 개수를 모두 더한다.

4-다양성의 값은 $S_4 = 3 + 3 = 6$이다.

5-다양성: 닷새로 이루어진 모든 구간에서 직원이 수행한 서로 다른 작업 유형의 개수를 모두 더한다.

5-다양성의 값은 $S_5 = 3$이다.