Задано число n и последовательность из n целых чисел. Рассмотрим все возможные циклические сдвиги заданной последовательности и отсортируем их в лексикографическом порядке. Необходимо вывести сумму длин наибольших общих префиксов соседних в этом порядке сдвигов.
Вход содержит не более 200 тестовых примеров. Каждый тестовый пример состоит из двух строк. Первая из них содержит целое число 1 ≤ n ≤ 50000 - количество магических башен. Вторая строка содержит n целых чисел в интервале от 0 до 100 - заданную последовательность.
Последний тест содержит n = 0 и не обрабатывается.
Для каждого теста в отдельной строке выведите искомую сумму.