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