好きな位置に持っていく操作を $A$、先頭に持っていく操作を $B$、末尾に持っていく操作を $C$ とする。
$A_i \lt B_i$ や $A_i \lt C_i$ なら先頭や末尾への移動でも $A$ を使った方がいいが、 その場合は $B_i,C_i$ を $A_i$ で上書きしておき、先頭や末尾への移動は常に $B,C$ を使うものとする。
つまり、上書きした上で $A_i \ge B_i,C_i$ と仮定をおいて問題ない。
1つの値は2回以上動かす必要は無い （もし同じ値を2回以上動かす操作手順があったとしたら、その最後の操作だけを行っても結果は変わらない） ので、結局、$1～N$ の各値に 「操作 $A$ を使う」「$B$ を使う」「$C$ を使う」「初期から移動させない」のどれかを割り振る問題となる。
移動させない値は初期から昇順に並んでいる必要があるが、コストが絡んでくるため最長増加部分列を残せばいいわけでもなく、何を残すべきか判断が難しい。
最適な移動をした場合、値は $1～N$ を順番に並べた中で3つの区間に分けられる。
4 1 6 3 5 2 → 2 4 1 6 3 5 2をBで移動 → 1 2 4 6 3 5 1をBで移動 → 1 2 4 3 5 6 6をCで移動 → 1 2 3 4 5 6 4をAで移動 1 2 | 3 4 5 | 6 (1) (2) (3)
必ず1つは動かさなくていい数字が存在するため、(2)は必ず存在する（(1)や(3)は、長さ0になる場合もある）。
また(2)の両端について、もしこれが $A$ によって動かされたものだとすると（$A_i \ge B_i,C_i$ の仮定があるため）、
左端なら(1)に、右端なら(3)に属させて悪くなることはない。
そのため、必ず(2)の両端は動かされていないとしてよい。
この両端を全探索すればよいのかなと思うが、そうするとそれだけで少なくとも $O(N^2)$ かかるためTLE。
ここで、(2)の最大値だけを固定するDPを考える。
(2)の最大値を固定すると(3)の総コストは他に依らず固定されるため、その部分は最後に足してもよい。
つまり、DPで管理するのは(1)(2)部分のみでよい。
$DP[1]～DP[i-1]$ から $DP[i]$ を $O(1)$ や $O(\log{N})$ 程度で計算できれば時間制約に間に合う。
最後に $DP[1]～DP[N]$ のそれぞれに(3)部分を合わせた中での最小値が答えである。
そして、$i$ が(2)の最大値になる場合というのは、以下の2通りに限られる。
値 $i$ の初期位置を $pos[i]$ とする。
この中での最小値を $DP[i]$ とすればよい。
一見、(b.)の計算に各 $j$ を調べる必要があり $O(N)$ かかってしまう気がするが、
上手いことセグメント木に載せれば、区間最小値を得るクエリによって $O(\log{N})$ で可能となる。
基本的な考え方は以下の通り。
$i$ を小さい方から処理して $DP[i]$ を求めたら、その情報をセグ木の $pos[i]$ に登録する。
すると、$k$ の処理時には、セグ木の $0～pos[k]-1$ の部分に、 「$j \lt k$ かつ $pos[j] \lt pos[k]$ であるような $f(j)$ の値」が入っている状態にできるので、この最小値を求めればよい。
P 4 1 6 3 5 2
セグ木初期
0 1 2 3 4 5
INF INF INF INF INF INF
i=4 まで処理
0 1 2 3 4 5
f(4) f(1) INF f(3) INF f(2)
|-----------------------|
DP[5] について求める際は、この部分の最小値を求めればよい
だが、$f(j)=DP[j]+A_{j+1} + A_{j+2} + ... + A_{i-1}$ は、一旦登録した後でも、$i$ が進むごとに変わっていってしまう。
これは困った。もちろん毎回書き換えている時間は無い。
だが少し考えると、変化量は一旦登録された値に対しては常に一定である。
$i$ を処理するたびにセグ木全体に $A_i$ を足し込んでやれば、正しい $f(j)$ を維持できる。
その場合、区間足し込みも必要になるので、遅延評価セグメント木を使うことで実現できる。
または、「これまでに足し込まれた総和 $Add[i]=A_1+A_2+...+A_{i}$」を別に持っておいて、
とすると、値は登録時のまま変えずともよくなり、通常のセグメント木でも実装できるので定数倍高速になる。