Reverse and Rejoin

Time limit3sMemory limit512 MB

Summary

Split a fixed sequence into two non-empty parts, reverse each part, and print the lexicographically smallest result among all split positions.

Level: Medium7 of 10
Topics: Array, String matching, Sorting, Implementation
Solved: No attempts yet

Problem

You are given a sequence of $N$ numbers. The same number can appear several times, and every number is a natural number smaller than $2^{31}$ .

Split the sequence into two parts, each of non-zero length, reverse the order inside each part, then join the two parts back in their original front to back order. Different split positions give different sequences. Print the sequence that comes first in lexicographic order among the sequences you can build this way.

In lexicographic order the sequence with the smaller first number comes first. If the first numbers are equal, the one with the smaller second number comes first, and if the second numbers are equal too, the third numbers decide, and so on. All sequences compared here have the same length.

Input

The first line has an integer $N$ ( $2 \le N \le 4 \times 10^6$ ). The second line has the $N$ numbers of the sequence in order, separated by spaces. Each number is a natural number smaller than $2^{31}$ .

Output

On the first line, print the sequence that comes first in lexicographic order among the sequences you can build. Print the $N$ numbers on one line, separated by single spaces.

Examples3

Example 1

Input

10
2 1 3 1 2 1 3 1 3 1

Expected output

1 2 1 3 1 2 1 3 1 3

Example 2
Input
```
2
5 3
```
Expected output
```
5 3
```
Example 3
Input
```
4
3 2 5 1
```
Expected output
```
2 3 1 5
```