本問題のテーマは、連続部分列の最大値の性質です。

各要素のスコアへの寄与を長方形の組み合わせで表す

値の等しい要素どうしは要素番号でタイブレークするとします。連続部分列 \((A_l,A_{l+1},\ldots ,A_r)\) の \(2\) 番目に大きい値が \(A_i\) となる条件は、\(l\leq i\leq r\) 、かつ連続部分列に \(A_i\) 以上の要素がちょうど \(2\) 個含まれることです。適切に場合分けすると、実現可能ならば \(l,r\) の条件がそれぞれ区間で表せます。

例えば、\(A_i\) 以上の要素の番号が順に \(k_1, k_2, k_3=i, k_4, k_5\) であったとすると、\(A_i\) が \(2\) 番目に大きい値となるのは以下のいずれかの場合です。

• \(k_1 \lt l \leq k_2\) かつ \(k_3 \leq r \lt k_4\)
• \(k_2 \lt l \leq k_3\) かつ \(k_4 \leq r \lt k_5\)

\(2\) 番目に小さい値についても同様です。

またこれらの区間の境界を求めるには、順序付き集合に \(A_i\) が大きい順（\(2\) 番目に小さい値については小さい順）に \(i\) を追加しながら周囲を探索するとよいです。計算量は \(O(N \log N)\) です。

連続部分列 \((A_l,A_{l+1},\ldots ,A_r)\) のスコアを \(s _ {l,r}\) とおきます。

ここで、\(N\times N\) のマス目の各マス \((l,r)\) のうち \(r-l+1 \geq 4\) を満たすマスに \(s _ {l,r}\) の値を書き込むことを考えます。\(N\times N\) マスがすべて \(0\) の状態から始めます。前述の方法で、\(A_i\) の寄与を高々 \(4\) 回の長方形領域への一様加算で表せるので、全体は高々 \(4N\) 回の長方形領域への一様加算で表せます。

遅延セグメント木を用いた DP

\(q_r\) (\(0\leq r\))を、\((A_1,A_2,\ldots ,A_r)\) を連続部分列に分割したときのスコアの総和の最大値（分割できない場合は \(-\infty\) ）とします。ただし、\(q_0=0\) とします。求めたい値は \(q_N\) です。

ある \(r\) を決めたとき、長さ \(N+1\) の数列 \(D=(D_0,D_1,\ldots ,D_N)\) を \(D_i=q_i+s_{i+1,r}\) で定めます。ただし定義できない部分の値は適当に埋めるとします。すると、\(4 \leq r\) のときの \(q_r\) は \(q_r=\max (D_0,D_1,\ldots ,D_{r-4})\) と表せます。

\(r\) を \(1\) だけ増加させたときの \(D\) の差分更新を考えます。\(D_i=q_i+s_{i+1,r}\) のうち \(q_i\) の部分は変化しないので \(s_{i+1,r}\) の変化のみ考えればよいですが、\(s _ {l,r}\) 全体は高々 \(4N\) 回の長方形領域への一様加算で表せるので、その差分は全体を通して高々 \(8N\) 回の区間一様加算になります。

各 \(q_r\) を求めた後は、管理上の空列のスコアを \(0\) として、次の開始点に対応する \(D_r=q_r\) を \(1\) 点変更で設定します。

以上により、区間一様加算・区間最大値を処理できる遅延セグメント木を用いて本問題を解けます。計算量は \(O(N \log N)\) です。