Smallest Permutation by Cyclic Shift

You are given an array of n integers. You can perform cyclic shifts on the array, which means moving the first element to the end of the array. You can perform one or more cyclic shifts. Your task is to determine the lexicographically smallest permutation that can be obtained by performing such cyclic shifts.

For example, if the array is [3, 1, 2, 4], the cyclic shifts are:

• [3, 1, 2, 4] (original array)
• [1, 2, 4, 3]
• [2, 4, 3, 1]
• [4, 3, 1, 2]

The lexicographically smallest permutation among these is [1, 2, 4, 3].

Note: Two arrays A and B are compared lexicographically: A is less than B if for the first position where they differ, the element in A is smaller than the corresponding element in B.

The problem can be mathematically stated as finding the minimum of the set { S_i : i = 0, 1, ..., n-1 } where S_i is the array after i cyclic shifts. In LaTeX, the problem can be written as:

Find \( \min \{ S_i : 0 \le i < n \} \), where each \( S_i \) is defined by a cyclic shift of the array \( A = [a_1, a_2, \dots, a_n] \) such that \( S_i = [a_{i+1}, a_{i+2}, \dots, a_n, a_1, a_2, \dots, a_i] \).

inputFormat

The input is read from standard input (stdin) and consists of two lines:

• The first line contains a single integer \( n \) representing the number of elements in the array.
• The second line contains \( n \) space-separated integers representing the elements of the array.

outputFormat

Output the lexicographically smallest permutation of the array obtained by performing one or more cyclic shifts. The output should be printed to standard output (stdout) as \( n \) space-separated integers on a single line.

## sample

4
3 1 2 4

1 2 4 3