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~.

Constraints

~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

6
2 4 3 1 6 5

Sample Output

1 2 4 3 5 6

Explanation

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.