Editorial

Replacement

Editorial

Every order of operations has the same total cost. The answer is

\sum_{i=1}^{N}P_i-\min_{1\leq i\leq N}P_i.

Compute the sum and minimum in one pass. The time complexity is $O(N)$ and the additional space complexity is $O(1)$ .

Proof

Replacing adjacent values $x,y$ with $\min(x,y)$ decreases the sum of the sequence by

x+y-\min(x,y)=\max(x,y),

y

−

min(x,y)=

max(x,y),

which is exactly the cost of the operation.

The total cost therefore equals the initial sum minus the final remaining value. Regardless of the order of operations, that value is the minimum of the original sequence, giving the formula above.