数列のソート 3

到達できる数列は巡回シフトのみである。$A_N$ の次を $A_1$ として下降箇所を数える。その個数が $1$ 以下のときに限り、その箇所で切れば整列できる。時間 $O(N)$。全回転の確認は $O(N^2)$。