Smallest Lexicographical Rotation

Given a sequence of n integers, your task is to determine the lexicographically smallest rotation of the sequence. A rotation of a sequence is obtained by moving some number of elements from the beginning to the end, maintaining their relative order. Formally, for a sequence \(a = [a_0,a_1,\dots,a_{n-1}]\), a rotation starting at index \(i\) produces the sequence \(a' = [a_i, a_{i+1}, \dots, a_{n-1}, a_0, a_1, \dots, a_{i-1}]\). Among all \(n\) possible rotations, the lexicographically smallest is defined as the one that is smallest in dictionary order. That is, for two sequences \(A=[A_0, A_1, \dots, A_{n-1}]\) and \(B=[B_0, B_1, \dots, B_{n-1}]\), we say \(A < B\) if there exists an index \(j\) (\(0 \leq j < n\)) such that \(A_k = B_k\) for all \(0 \leq k < j\) and \(A_j < B_j\).

Your program should read the input from stdin and print the lexicographically smallest rotation of the sequence to stdout using space-separated integers.

inputFormat

The first line of input contains a single integer \(n\) (\(1 \leq n \leq 10^5\)), representing the number of integers in the sequence.

The second line contains \(n\) space-separated integers.

outputFormat

Output the lexicographically smallest rotation of the sequence as \(n\) space-separated integers in one line.

5
3 1 2 4 5

1 2 4 5 3