eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Башти

Башти

Ліміт часу 4 секунди
Ліміт використання пам'яті 64 MiB

Задано число n та послідовнісь із n цілих чисел. Розглянемо усі можливі циклічні зсуви заданої послідовності та відсортуємо їх у лексикографічному порядку. Необхідно вивести суму довжин найбільших спільних префіксів сусідніх у цьому порядку зсувів.

Вхідні дані

Вхід містить не більше 200 тестів. Кожний тест складається з двох рядків. Перший рядок містить кількість магічних башт n (1n50000). Другий рядок містить n цілих чисел в інтервалі від 0 до 100 - задану послідовність.

Останній тест містить n = 0 та не обробляється.

Вихідні дані

Для кожного тесту виведіть в окремому рядку шукану суму.

Приклад

Вхідні дані #1
11
12 8 18 18 8 18 18 8 15 15 8
0
Вихідні дані #1
13