19872번 - Борьба с рутиной 서브태스크다국어

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

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

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

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

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

Во второй строке находится n целых чисел a₁, a₂, . . . , a_n — типы заданий, которое выполнял сотрудник (1 ≤ a_i ≤ 10⁹).

Выведите n целых чисел: S₁, S₂, . . . , S_n.

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

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

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

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

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

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

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

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

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

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

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