Мелодии комуза


Отправить решение Решать в редакторе

Сложность: 70%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 512M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Комуз — трёхструнный щипковый инструмент, символ кыргызской музыки. Студентка консерватории Жибек записала кюй (инструментальную пьесу) как последовательность из n нот; каждая нота обозначена целым числом — её частотой в сотых долях герца.

Мотивом назовём любой непрерывный фрагмент мелодии, то есть последовательность нот a[l], a[l+1], …, a[r]. Два мотива одинаковы, если они имеют одну длину и совпадают нота в ноту, где бы в мелодии они ни встречались.

Жибек разучивает пьесу постепенно: сначала первую ноту, потом первые две, потом первые три и так далее. После разучивания каждого начала мелодии ей интересно, сколько различных мотивов она уже умеет играть. Для каждого i от 1 до n выведите количество различных мотивов в начале мелодии a[1], …, a[i].

Входные данные

В первой строке — целое число n (1 ≤ n ≤ 500 000).

Во второй строке — n целых чисел a[1], …, a[n] (1 ≤ a[i] ≤ 10⁹).

Выходные данные

Выведите n строк: в i-й строке — количество различных мотивов в начале мелодии длины i.

Пример 1

Вход:

5
440 494 440 494 440

Выход:

1
3
5
7
9

Пример 2

Вход:

4
7 7 7 7

Выход:

1
2
3
4

Пояснение

В первом примере начало 440 494 440 содержит мотивы 440, 494, 440 494, 494 440, 440 494 440 — всего 5 различных (мотив 440 встречается дважды, но считается один раз).

Во втором примере каждое новое начало добавляет ровно один новый мотив — самый длинный.

Система оценивания

Подзадача Баллы Дополнительные ограничения
1 15 n ≤ 1000
2 25 все ноты — числа от 1 до 26
3 60 без дополнительных ограничений

Баллы за подзадачу начисляются, только если пройдены все её тесты.

Примечание

Ответы могут превышать 2³¹ — используйте 64-битные целые числа.


Комментарии

Еще нет ни одного комментария.