|
Борьба с рутиной
(Время: 2 сек. Память: 16 Мб Сложность: 52%)
Важным элементом повышения эффективности работы сотрудников является борьба с рутиной. Построим математическую модель разнообразия типов заданий, выполняемых сотрудником в компании.
Рассмотрим работу сотрудника в течение n последовательных рабочих дней. Будем считать, что
каждый день сотрудник выполняет ровно один тип заданий, обозначим тип заданий, выполняемый
сотрудником в i-й день, целым числом ai.
Для оценки рутинности работы сотрудника будем использовать следующую характеристику.
Зафиксируем целое число d и рассмотрим все отрезки из d подряд идущих рабочих дней. Для каждого такого отрезка найдём количество различных типов заданий, которые работник выполнял на
протяжении этих дней, и просуммируем эти значения. Полученную величину обозначим как Sd и
будем называть её d-разнообразием. Чем d-разнообразие выше, тем больше различных типов заданий выполнял сотрудник. Профилем вариативности сотрудника будем называть массив значений [S1, S2, ... , Sn].
Требуется написать программу, которая по заданной последовательности a1, a2, ... , an типов выполняемых сотрудником заданий вычисляет его профиль вариативности.
Входные данные
В первой строке входного файла INPUT.TXT находится единственное целое число n — количество последовательных рабочих
дней, которые необходимо проанализировать (1 ≤ n ≤ 2×105).
Во второй строке находится n целых чисел a1, a2, ... , an — типы заданий, которое выполнял сотрудник (1 ≤ ai ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите n целых чисел: S1, S2, ... , Sn.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5
1 3 2 1 2 | 5 8 8 6 3 |
| 2 | 3
10 10 10 | 3 2 1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
