P2513切序列 | |
|
Description
给定一个非负整数序列{A1,A2,...,An},保证A1>A2, ..., An。
现在需要你要把它切成三段,每段序列长度>=1。把每段序列翻转。再把翻转后的三段序列按原顺序重新拼接。
要求使新的序列的"字典序"尽可能小。
Input Format
第一行一个正整数n。
接下来n行每行一个数,依次表示序列的每一个数字。
Output Format
共n行,每行一个数。依次表示新序列的每一个数字。
Sample Input 1
5
10
1
2
3
4
Sample Output 1
1
10
2
4
3
Sample Input 2
7
10
0
2
2
2
2
3
Sample Output 2
0
10
2
2
2
2
3
Sample Input 3
8
5
0
3
1
2
3
1
4
Sample Output 3
0
5
1
3
2
1
3
4
Sample Input 4
9
100
80
1
2
2
81
1
2
2
Sample Output 4
1
80
100
1
81
2
2
2
2
Hint
对于100%的数据:n ≤ 200000 0<=Ai<=1000000000
样例1解释
{10,1,2,3,4} 切割-> {10,1} {2} {3,4} 翻转 -> {1,10}{2}{4,3} 拼接 -> {1,10,2,4,3}
1<=Ai<=109
Source poj 3581