Yaroslav and Productivity

The important move is to stop tracking individual operations on individual elements. The post positions are the only boundaries where two neighboring elements can behave differently.

Turn the prefixes into blocks

Sort the post positions:

$c_1<c_2<\dots<c_m,$

and define $c_0=0$. These positions divide the array into the following blocks:

$B_i=[c_{i-1}+1,c_i]\qquad (1\le i\le m),$

followed by the suffix

$B_{m+1}=[c_m+1,n].$

Let the sum of block $B_i$ be $S_i$.

Consider two elements in the same block $B_i$. There is no post position between them, so every chosen prefix either contains both elements or contains neither. They therefore receive exactly the same number of sign changes. The final contribution of the whole block is consequently either

$S_i$

or

$-S_i.$

The suffix $B_{m+1}$ is different: every available prefix ends at or before $c_m$, so this suffix is never changed. Its contribution is permanently $S_{m+1}$, even if that number is horribly negative. No magical absolute value there.

The apparently coupled signs are actually independent

A post at $c_i$ flips exactly the blocks

$B_1,B_2,\dots,B_i.$

At first this looks annoying: one operation changes several block signs. However, any desired signs for $B_1,\dots,B_m$ can be constructed by processing blocks from right to left.

Start with $B_m$. Among operations not yet decided, only the post at $c_m$ can change its sign, so use that post exactly when necessary to give $B_m$ its desired sign.

Next handle $B_{m-1}$. The earlier decision at $c_m$ may already have flipped it, but the post at $c_{m-1}$ lets us either keep or toggle its current sign. Crucially, this post ends before $B_m$, so it cannot ruin the sign already fixed for $B_m$.

Continue in the same way down to $B_1$. Thus every block sign can be chosen independently.

The same fact can be written algebraically. If $y_i\in\{0,1\}$ says whether the post at $c_i$ is read, then the final sign of $B_i$ is

$\sigma_i=(-1)^{y_i+y_{i+1}+\dots+y_m}.$

Given any desired $\sigma_1,\dots,\sigma_m$, set $\sigma_{m+1}=1$ and choose $y_i$ so that

$(-1)^{y_i}=\sigma_i\sigma_{i+1}.$

So there really is no hidden compatibility condition. Nested prefixes were just wearing a fake mustache.

Choosing the optimal signs

For every flippable block $B_i$, its contribution can only be $S_i$ or $-S_i$. Neither can exceed $|S_i|$, and because all block signs are independently achievable, we can attain $|S_i|$ for every $i\le m$ simultaneously.

Therefore,

$\text{answer}=\sum_{i=1}^{m}|S_i|+S_{m+1}.$

This gives both sides of the proof:

• Upper bound: each flippable block contributes at most its absolute sum, and the suffix is fixed.
• Attainability: choose the sign of each flippable block to make its sum nonnegative; the right-to-left construction realizes all those choices.

Hence the formula is optimal.

Computing block sums

Build prefix sums

$P[0]=0,\qquad P[i]=\sum_{k=1}^{i}a_k.$

Then

$S_i=P[c_i]-P[c_{i-1}]$

for $1\le i\le m$, while

$S_{m+1}=P[n]-P[c_m].$

The final formula is

$\boxed{\sum_{i=1}^{m}\left|P[c_i]-P[c_{i-1}]\right|+P[n]-P[c_m]}.$

For the first sample, the sorted post positions are $1,3,5$. The corresponding block sums are $-1,-1,-1$, and there is no remaining suffix. Their absolute values sum to $3$.

For the third sample, the only flippable block has sum $-10$, while the untouchable suffix has sum $-5$. The answer is therefore $|-10|+(-5)=5$. This is exactly why taking the absolute value of the suffix would be bogus.

Correctness proof

Lemma 1. Each block $B_i$ for $1\le i\le m$ contributes either $S_i$ or $-S_i$, while $B_{m+1}$ always contributes $S_{m+1}$.

Proof. All elements of $B_i$ belong to exactly the same available prefixes, so every chosen operation flips all of them together. No available prefix contains any element after $c_m$. Therefore the stated contributions follow. $\square$

Lemma 2. Every assignment of signs to $B_1,\dots,B_m$ is achievable.

Proof. Process $i=m,m-1,\dots,1$. At step $i$, choose whether to use the post at $c_i$ so that $B_i$ gets its desired sign. This operation does not touch any block $B_j$ with $j>i$, and later operations have even smaller endpoints, so no already-fixed sign changes. All desired signs are obtained. $\square$

Theorem. The algorithm outputs the maximum possible total productivity.

Proof. By Lemma 1, each $B_i$ with $i\le m$ contributes at most $|S_i|$, and the suffix contributes exactly $S_{m+1}$. Thus no result exceeds $\sum_{i=1}^{m}|S_i|+S_{m+1}$. By Lemma 2, we can choose every flippable block's sign so that it contributes $|S_i|$, attaining this bound. The algorithm computes precisely that value. $\square$

Complexity

Sorting costs $O(m\log m)$, and building and scanning the prefix sums costs $O(n+m)$. The total time is $O(n+m\log m)$ per test case, with $O(n+m)$ memory.

Use long long: sums can have magnitude around $2\cdot 10^{14}$, which absolutely does not fit in a 32-bit int.