DMOPC '21 Contest 10 P2 - Cycle Sort

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Bored of studying physics, Fumino decides to take a break with a brainteaser!

Nariyuki gave her a permutation of the first natural numbers, arranged into a line. She can rotate the list however she likes. That is, she can perform this move freely: take the first element of the list and move it to the back.

Nariyuki challenges her to get the lexicographically-smallest list. This is, of course, much too easy. Thus, Nariyuki allows her to perform at most one swap.

Suddenly the problem is much too hard for Fumino! She comes to you, Rizu, for help since you are good at such puzzles. Can you help her?

Definition: An array is lexicographically smaller than an array if and at the first index where , .

Constraints

All are pairwise distinct.

Input Specification

The first line contains .

The next line contains space-separated integers .

Output Specification

Output the lexicographically smallest array that can be created according to the puzzle's rules.

Sample Input

6
2 4 3 1 6 5

Sample Output

1 2 4 3 5 6

Explanation

Swapping the with the and rotating the array produces 1 2 4 3 5 6, which can be proven to be the lexicographically smallest output.