\(A_i \leq A_{i+1} \leq \cdots \leq A_N\) をみたす最小の \(i\) を \(k\) とおきます．

まず明らかに \(k-1\) 回の rotate 操作が必要です．

rotate 操作を \(x\) (\(k-1 \leq x\)) 回行う場合の操作回数の最小値を考えます． rotate 操作だけを \(x\) 回行った後の列を \(b_1,b_2,\cdots,b_N\) とします． ここで，目標とする列 \(c_1,c_2,\cdots,c_N\) は，\(c_i=\max_{1 \leq j \leq i}b_j\) としてよいです． rotate の過程で一度でも先頭に来たことがある値は，自由に増やすことができます． \(x < N\) のときは，先頭に来たことがない値がありますが，\(A_{x+1} \leq \cdots \leq A_N\) であり，これらの値を増やす必要はないため，問題ありません．

結局，予め \(A\) を \(k-1\) 回 rotate したあとで，各 \(0 \leq x <N\) について以下の問題を解けばよいです．

• \(\sum_{1 \leq i \leq N} \max (A_{x+1},A_{x+2},\cdots,A_{x+i})\) を求める．

ただしここで，\(A_{N+i}=A_i\) としています． \(M=\max(A_1,A_2,\cdots,A_N)\) とします． 上の問題は，以下のように変形すると見通しが良くなります．

• \(\sum_{1 \leq i \leq 2N-x} \max (A_{x+1},A_{x+2},\cdots,A_{x+i})-M \times (N-x)\) を求める．

\(\sum_{1 \leq i \leq 2N-x} \max (A_{x+1},A_{x+2},\cdots,A_{x+i})\) の部分は有名問題で，stack を持ちながら \(A\) を後ろから見ていって求めることができます．

計算量は全体で\(O(N)\) です．

解答例(c++)