Задачі
Башти
Башти
Задано число n та послідовнісь із n цілих чисел. Розглянемо усі можливі циклічні зсуви заданої послідовності та відсортуємо їх у лексикографічному порядку. Необхідно вивести суму довжин найбільших спільних префіксів сусідніх у цьому порядку зсувів.
Вхідні дані
Вхід містить не більше 200 тестів. Кожний тест складається з двох рядків. Перший рядок містить кількість магічних башт n (1 ≤ n ≤ 50000). Другий рядок містить n цілих чисел в інтервалі від 0 до 100 - задану послідовність.
Останній тест містить n = 0 та не обробляється.
Вихідні дані
Для кожного тесту виведіть в окремому рядку шукану суму.
Приклад
Вхідні дані #1
11 12 8 18 18 8 18 18 8 15 15 8 0
Вихідні дані #1
13