Lexicographically smallest cyclic shift
Lexicographically smallest cyclic shift
A permutation of order n is a sequence of pairwise distinct positive integers p1
, p2
, ..., pn
, where each 1 ≤ pi
≤ n. We say that the permutation q1
, q2
, ..., qn
is lexicographically less than the permutation p1
, p2
, ..., pn
if there is i such that qi
< pi
, and for any j < ipj
= qj
.
A cyclic shift by k of a permutation p1
, p2
, ..., pn
is the sequence pk+1
, pk+2
, ..., pn
, p1
, ..., pk
. Note that any cyclic shift of a permutation is also a permutation.
Find the lexicographically smallest cyclic shift of the given permutation.
Input
The first line contains the order n (1 ≤ n ≤ 105
) of the given permutation. The second line contains numbers p1
, p2
, ..., pn
.
Output
Print the permutation that is the smallest lexicographically cyclic shift of the permutation given in the input. Use the same format as the permutation given in the second line of the input.
3 3 2 1
1 3 2