Наступна перестановка

Знайдіть наступну перестановку. Вважайте, що за перестановкою $(n,n-1,...,2,1)$ йде тотжня перестановка $(1,2,...,n-1,n)$.

Вхідні дані

Перший рядок містить кількість $n(1\le n\le 10^5)$ елементів у перестановці. Другий рядок містить перестановку з $n$ чисел.

Вихідні дані

Виведіть $n$ чисел — наступну перестановку для заданої.

Приклади