Let \(f(k)\) be the minimum sum of \(A'=(A_1,A_2,\ldots,A_k)\) after performing an operation on \(A'\) when choosing \(x\) such that \(x \leq k\).

Also, let \(g(k)\) be the minimum sum of \(A''=(A_{N-k+1},\ldots,A_N)\) after performing an operation on \(A''\) when choosing \(y\) such that \(y \leq k\).

If we can enumerate \(f(0),f(1),\ldots,f(N),g(0),g(1),\ldots, g(N)\), the answer can be found as \(\mathrm{min} f(i) + g(N-i)\).

We explain how to \(f\); same applies to \(g\).

We have \(f(0)=0\). We want to find \(f(k+1)\) when we have \(f(k)\) and preceding terms. It depends on whether \(x<k+1\).

• If \(x<k+1\):

The minimum sum is \(f(k) + A_{k+1}\).

• If \(x=k+1\):

The minimum sum is \(L(k+1)\).

Thus, we find \(f(k+1) = \mathrm{min}(f(k) + A_{k+1}, L(k+1))\).

Therefore, the problem has been solved in a total of \(\mathrm{O}(N)\) time.