The theme of this problem is the properties of maximum values in contiguous subsequences.

Expressing each element’s contribution to the score with rectangles

Break ties between equal elements by their indices. The second largest value of a contiguous subsequence \((A_l,A_{l+1},\ldots ,A_r)\) is \(A_i\) if and only if \(l\leq i\leq r\) and the subsequence contains exactly \(2\) elements at least \(A_i\). With an appropriate case analysis, each feasible case gives interval conditions for \(l,r\) separately.

For example, suppose the indices of elements at least \(A_i\) are, in order, \(k_1, k_2, k_3=i, k_4, k_5\). Then \(A_i\) is the second largest value in either of the following cases:

• \(k_1 \lt l \leq k_2\) and \(k_3 \leq r \lt k_4\).
• \(k_2 \lt l \leq k_3\) and \(k_4 \leq r \lt k_5\).

The second smallest value can be handled similarly.

To find the boundaries of these intervals, insert indices \(i\) into an ordered set in decreasing order of \(A_i\) (in increasing order for the second smallest value), and examine the neighboring indices. This takes \(O(N \log N)\) time.

Write \(s _ {l,r}\) for the score of the contiguous subsequence \((A_l,A_{l+1},\ldots ,A_r)\).

Consider an \(N\times N\) grid. Write \(s _ {l,r}\) in each cell \((l,r)\) satisfying \(r-l+1 \geq 4\). Start with all \(N\times N\) cells set to \(0\). With the method above, the contribution of \(A_i\) can be expressed using at most \(4\) uniform additions to rectangular regions. Therefore, the whole score table can be expressed using at most \(4N\) uniform additions to rectangular regions.

DP using a lazy segment tree

Let \(q_r\) (\(0\leq r\)) be the maximum total score when partitioning \((A_1,A_2,\ldots ,A_r)\) into contiguous subsequences, or \(-\infty\) if no valid partition exists. Define \(q_0=0\). The value we want is \(q_N\).

For a fixed \(r\), define a sequence \(D=(D_0,D_1,\ldots ,D_N)\) of length \(N+1\) by \(D_i=q_i+s_{i+1,r}\). Fill entries that cannot be defined with suitable values. Then, for \(4 \leq r\), we have \(q_r=\max (D_0,D_1,\ldots ,D_{r-4})\).

Consider updating \(D\) when \(r\) increases by \(1\). In \(D_i=q_i+s_{i+1,r}\), the \(q_i\) part does not change, so we only need to consider the change in \(s_{i+1,r}\). Since the entire table \(s _ {l,r}\) can be expressed using at most \(4N\) uniform additions to rectangular regions, its changes throughout the sweep can be expressed using at most \(8N\) uniform range additions.

After computing each \(q_r\), treat the empty sequence as having score \(0\) for bookkeeping, and set \(D_r=q_r\), corresponding to the next starting point, with an update to \(1\) element.

Thus, a lazy segment tree supporting uniform range addition and range maximum queries solves the problem. The time complexity is \(O(N \log N)\).