# Sequence

Time Limit: 5000MS

Memory Limit: 65536K

## Description

Given a sequence, {A1, A2, ..., An} which is guaranteed A1 > A2, ..., An,  you are to cut it into three sub-sequences and reverse them separately to form a new one which is the smallest possible sequence in alphabet order. The alphabet order is defined as follows: for two sequence {A1, A2, ..., An} and {B1, B2, ..., Bn}, we say {A1, A2, ..., An} is smaller than {B1, B2, ..., Bn} if and only if there exists such i ( 1 ≤ in) so that we have Ai < Bi and Aj = Bj for each j < i.

## Input

The first line contains n. (n ≤ 200000)The following n lines contain the sequence.

## Output

output n lines which is the smallest possible sequence obtained.

## Sample Input

5
10
1
2
3
4


## Sample Output

1
10
2
4
3


## Hint

{10, 1, 2, 3, 4} -> {10, 1 | 2 | 3, 4} -> {1, 10, 2, 4, 3}

## Source

POJ Founder Monthly Contest – 2008.04.13, Yao