Магічні башти

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

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

Вхідні дані

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

Вихідні дані

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

Приклади