Sequence
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 ≤ i ≤ n) 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.
5
10
1
2
3
4
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 Jinyu