Сдвиг перестановки

Перестановкой порядка n называется последовательность из попарно различных целых положительных чисел p₁, p₂, ... , p_n, где каждое 1 ≤ p_i ≤ n. Будем говорить, что перестановка q₁, q₂, ... , q_n лексикографически меньше перестановки p₁, p₂, . . . , p_n, если существует такое i, что q_i < p_i, а для любого j < i p_j = q_j .

Циклическим сдвигом на k перестановки p₁, p₂, ... , p_n называется последовательность, p_k+1, p_k+2, ... , p_n, p₁, ... , p_k. Исходная перестановка также считается своим циклическим сдвигом. Отметим, что любой циклический сдвиг перестановки также является перестановкой.

Ваша задача состоит в том, чтобы найти наименьший лексикографически циклический сдвиг заданной перестановки.

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

Первая строка входного файла INPUT.TXT содержит порядок n (1 ≤ n ≤ 10⁵) заданной перестановки. Вторая строка содержит числа p₁, p₂, ... , p_n, отделенные друг от друга пробелами.

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

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

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]