eolymp
Competitions

2022 Azerbaijan Round 1, 8-9-10-11 classes

Lexicographically smallest cyclic shift

A permutation of order n is a sequence of pairwise distinct positive integers p1, p2, ..., pn, where each 1pin. 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 (1n105) 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.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3
3 2 1
Output example #1
1 3 2