Башти

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

Вхідні дані

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

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

Вихідні дані

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

Приклади