Магические башни

Задано число n и последовательность из n чисел.

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

Входные данные

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

Выходные данные

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

Примеры