DMOPC '21 Contest 10 P2 - Cycle Sort

View as PDF

Submit solution

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

Problem type

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

Nariyuki gave her a permutation of the first N 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 A is lexicographically smaller than an array B if A \ne B and at the first index i where A_i \ne B_i, A_i < B_i.


1 \le N \le 10^6

1 \le a_i \le N

All a_i are pairwise distinct.

Subtask 1 [10%]

1 \le N \le 500

Subtask 2 [50%]

1 \le N \le 5 \times 10^3

Subtask 3 [40%]

No additional constraints.

Input Specification

The first line contains N.

The next line contains N space-separated integers a_i.

Output Specification

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

Sample Input

2 4 3 1 6 5

Sample Output

1 2 4 3 5 6


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


There are no comments at the moment.