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.
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}
Submit