Мелодии комуза
Комуз — трёхструнный щипковый инструмент, символ кыргызской музыки. Студентка консерватории Жибек записала кюй (инструментальную пьесу) как последовательность из 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-битные целые числа.
Комментарии