Попередня перестановка

Знайдіть попередню у лексикографічному порядку перестановку.

Перестановка виду N, N-1, ..., 3, 2, 1 є попередньою для 1, 2, 3, ..., N-1, N.

Вхідні дані

У першому рядку вхідного файлу записано число N (1 ≤ N ≤ 10^5) - кількість елементів у перестановці. У другому рядку записана перестановка.

Вихідні дані

У вихідний файл вивести N чисел - шукану перестановку.

Приклади