시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

Важным элементом повышения эффективности работы сотрудников является борьба с рутиной. Построим математическую модель разнообразия типов заданий, выполняемых сотрудником в компании.

Рассмотрим работу сотрудника в течение n последовательных рабочих дней. Будем считать, что каждый день сотрудник выполняет ровно один тип заданий, обозначим тип заданий, выполняемый сотрудником в i-й день, целым числом ai.

Для оценки рутинности работы сотрудника будем использовать следующую характеристику. Зафиксируем целое число d и рассмотрим все отрезки из d подряд идущих рабочих дней. Для каждого такого отрезка найдём количество различных типов заданий, которые работник выполнял на протяжении этих дней, и просуммируем эти значения. Полученную величину обозначим как Sd и будем называть её d-разнообразием. Чем d-разнообразие выше, тем больше различных типов заданий выполнял сотрудник. Профилем вариативности сотрудника будем называть массив значений [S1, S2, . . . , Sn].

Требуется написать программу, которая по заданной последовательности a1, a2, . . . , an типов выполняемых сотрудником заданий вычисляет его профиль вариативности.

입력

В первой строке находится единственное целое число n — количество последовательных рабочих дней, которые необходимо проанализировать (1 ≤ n ≤ 2 · 105).

Во второй строке находится n целых чисел a1, a2, . . . , an — типы заданий, которое выполнял сотрудник (1 ≤ ai ≤ 109).

출력

Выведите n целых чисел: S1, S2, . . . , Sn.

서브태스크

번호 배점 조건
1 12

1 ≤ n ≤ 50

1 ≤ ai ≤ 50

2 10

1 ≤ n ≤ 50

1 ≤ ai ≤ 109

3 10

1 ≤ n ≤ 500

1 ≤ ai ≤ 109

4 12

1 ≤ n ≤ 5000

1 ≤ ai ≤ 5000

5 10

1 ≤ n ≤ 5000

1 ≤ ai ≤ 109

6 16

1 ≤ n ≤ 2·105

1 ≤ ai ≤ 50

7 30

1 ≤ n ≤ 2·105

1 ≤ ai ≤ 109

예제 입력 1

5
1 3 2 1 2

예제 출력 1

5 8 8 6 3

예제 입력 2

3
10 10 10

예제 출력 2

3 2 1

힌트

Рассмотрим, как вычисляются значения Sd в первом примере.

1-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из одного дня.

Отрезок дней Типы заданий Количество различных
1 - 1 1 1
2 - 2 3 1
3 - 3 2 1
4 - 4 1 1
5 - 5 2 1

Значение 1-разнообразия равно S1 = 1 + 1 + 1 + 1 + 1 = 5.

2-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из двух дней.

Отрезок дней Типы заданий Количество различных
1 - 2 1, 3 2
2 - 3 3, 2 2
3 - 4 2, 1 2
4 - 5 1, 2 2

Значение 2-разнообразия равно S2 = 2 + 2 + 2 + 2 = 8.

3-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из трех дней.

Отрезок дней Типы заданий Количество различных
1 - 3 1, 3, 2 3
2 - 4 3, 2, 1 3
3 - 5 2, 1, 2 2

Значение 3-разнообразия равно S3 = 3 + 3 + 2 = 8.

4-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из четырех дней.

Отрезок дней Типы заданий Количество различных
1 - 4 1, 3, 2, 1 3
2 - 5 3, 2, 1, 2 3

Значение 4-разнообразия равно S4 = 3 + 3 = 6.

5-разнообразие: необходимо просуммировать количество различных типов заданий, выполняемых сотрудником по всем отрезкам, состоящим из пяти дней.

Отрезок дней Типы заданий Количество различных
1 - 5 1, 3, 2, 1, 2 3

Значение 5-разнообразия равно S5 = 3.

채점 및 기타 정보

  • 예제는 채점하지 않는다.