input
9
9 -2 8 1 1 8 1 1 1

output:
-2 9 1 1 8 1 1 1 8


input
9
9 -2 8 1 1 8 1 1 2

output
-2 9 1 1 8 1 1 8 2

tip:
(1) 因为A[1]>A[2~n],所以我们对A[] reverse后，求出sa[]后：
选择sa[i]>1 && (i为最小）对应的sa[i]作为第一个part必定是最优的
(2) 经过（1）操作后，剩下的问题变成了给出一个a[1～n]，求分成两部分并分别revese后再重组后的a'[]的字典序最小。。。。
这部分稍微动下脑筋就出来了，就不废话了= =
https://github.com/halfapri/half/blob/master/borc/string/poj3581/A.cpp