eolymp
bolt
Try our new interface for solving problems
Problems

Lexicographically smallest cyclic shift

Lexicographically smallest cyclic shift

Time limit 1 second
Memory limit 128 MiB

A permutation of order n is a sequence of pairwise distinct positive integers p[1], p[2], ..., p[n], where each 1p[i]n. We say that the permutation q[1], q[2], ..., q[n] is lexicographically less than the permutation p[1], p[2], ..., p[n] if there is i such that q[i] < p[i], and for any j < ip[j] = q[j].

A cyclic shift by k of a permutation p[1], p[2], ..., p[n] is the sequence p[k+1], p[k+2 ], ..., p[n], p[1], ..., p[k]. Note that any cyclic shift of a permutation is also a permutation.

Find the lexicographically smallest cyclic shift of the given permutation.

Input data

The first line contains the order n (1n10^5) of the given permutation. The second line contains numbers p[1], p[2], ..., p[n].

Output data

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.

Examples

Input example #1
3
3 2 1
Output example #1
1 3 2