Вам дана перестановка из первых N натуральных чисел. Найдите по ней следующую в лексикографическом порядке (будем считать, что за перестановкой N N-1 ... 3 2 1 следует тождественная перестановка, то есть, 1 2 3 ... N).
Входные данные
В первой строке входных данных содержится число N (1 <= N <= 10000). Во второй строке находится перестановка (последовательность натуральных чисел от 1 до N, разделенных пробелами).
Выходные данные
Требуется вывести искомую перестановку.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
1 3 2 |
2 1 3 |