数列 \(A'=(A_1,A_2,\ldots,A_k)\) にたいして \(x \leq k\) なる \(x\) を選んで操作を行ったときの \(A'\) の総和の最小値を \(f(k)\) とします。

また、数列 \(A''=(A_{N-k+1},\ldots,A_N)\) にたいして \(y \leq k\) なる \(y\) を選んで操作を行ったときの \(A''\) の総和の最小値を \(g(k)\) とします。

\(f(0),f(1),\ldots,f(N),g(0),g(1),\ldots, g(N)\) が列挙できれば、答えは \(\mathrm{min} f(i) + g(N-i)\) で求められます。

\(g\) についても同様なので、以下では \(f\) の求め方を考えます。

\(f(0)=0\) です。\(f(k)\) まで求まっているときに \(f(k+1)\) が高速に求まればよいです。\(x<k+1\) かどうかで場合分けをします。

• \(x<k+1\) のとき

総和の最小値は \(f(k) + A_{k+1}\) です。

• \(x=k+1\) のとき

総和の最小値は \(L(k+1)\) です。

よって \(f(k+1) = \mathrm{min}(f(k) + A_{k+1}, L(k+1))\) と求められました。

以上よりこの問題を \(\mathrm{O}(N)\) で解くことができました。