\begin{problem}{Башни}{towers.in}{towers.out}{4 секунды}{64 мебибайта}

Задано число $n$ и последовательность из $n$ чисел. Требуется
рассмотреть все возможные циклические сдвиги заданной последовательности,
отсортировать их в лексикографическом порядке, и вывести сумму 
наибольших общих префиксов соседних в этом порядке сдвигов.

\InputFile

Входной файл содержит не более $200$ тестовых примеров. Каждый
тестовый пример состоит из двух строк. Первая из них содержит 
целое число $1\leq n\leq 50000$ --- количество магических башен.
Вторая строка содержит $n$ чисел в интервале от $0$ до $100$ --- 
заданную последовательность.

После последнего тестового примера вместо числа $n$ идет~$0$.

\OutputFile

Для каждого тестового примера выведите одно число --- искомую сумму.

\Example

\begin{example}
\exmp{
11
12 8 18 18 8 18 18 8 15 15 8
0
}{
13
}%
\end{example}

\end{problem}
