N. Следующая перестановка

Дана перестановка чисел от 1 до $N$. Выведите следующую за ней в лексикографическом порядке или сообщите, что она последняя.

Перебирать перестановки нельзя: при $N = 10^5$ их немыслимо много, а ответ получается за один проход по массиву.

Приём такой: найти самый правый элемент, за которым идёт что-то большее; обменять его с наименьшим из больших справа; развернуть остаток. Именно это делает std::next_permutation, и полезно уметь написать это руками.

Первая строка содержит число $N$ ($1 \le N \le 10^5$).

Вторая строка содержит перестановку чисел от 1 до $N$.

Следующая перестановка через пробел или число $-1$, если данная перестановка последняя.