Prefix Reverse

解説

$Q_1, Q_2, \dots, Q_i$ を $Q_i, Q_{i-1}, \dots, Q_1$ に同時に置き換えることを長さ $i$ の反転と呼ぶ。

$k$ 回目の操作で反転すると $Q_1 = k$ となる。操作を行った後、 $Q_1 = P_1$ となる必要があるため、最後の反転は $k = P_1$ での操作である。

反転が $1$ 回だけの場合、条件を満たすように行えるのは長さ $1$ の反転のみであり、スコア $A_1$ を得られる。

反転が $2$ 回以上の場合を考える。最初の反転が長さ $L$ とすると、その後に $k = P_1$ での反転をする必要があるので $P_L \lt P_1$ である。よって、 $P_1 = \max(P_1, \dots, P_L)$ かつ $P_L = \min(P_1, \dots, P_L)$ が必要である。この反転で、 $Q_L = P_1$ となる。

$k \lt P_1$ となる $k$ において反転するとき、反転する前は $Q_1 \lt k$ であるため、反転する範囲に $P_1$ は含まれず、$Q_L = P_1$ のままである。

よって、最後の反転は長さ $L$ の反転であるため、その直前では $Q = (P_L, P_{L-1}, \dots, P_1, P_{L+1}, P_{L+2}, \dots, P_N)$ である。しかし、 $2$ 回の長さ $L$ の反転の間に別の反転をすると $P_L < Q_1$ となってしまう。したがって、反転する回数はちょうど $2$ 回であるとわかる。

以上より、答えは次の条件を満たす $L$ に対する $2A_L$ の最大値と、 $A_1$ の大きい方である。

• $2 \le L \le N$
• $P_1 = \max(P_1, \dots, P_L)$
• $P_L = \min(P_1, \dots, P_L)$

$P$ の先頭から順に、累積最小値・最大値を持つことで各 $L$ に対して条件を満たすかを $O(1)$ で判定すると、全体で $O(N)$ で解くことができる。