Careful Deletion

Cost for a fixed last position

Let $k$ be the original position of the last deleted element. Every element to its left must be deleted from the front, and every element to its right must be deleted from the back. If position $k$ can remain last, its cost is therefore

$$C(k)=\sum_{i<k}L_{P_i}+\sum_{i>k}R_{P_i}+\min(L_{P_k},R_{P_k}).$$

Exchanging deletions

Let $x$ be an endpoint that can currently be deleted. Until deleted, it remains at that endpoint and remains an extreme value. In any complete deletion order, move the deletion of $x$ to the beginning. All other deletions remain legal: removing an element cannot destroy another element's extreme-value property, and deletions from the opposite end still work. The direction used for the final element may change, so use this argument only for feasibility.

Consequently, deleting any currently eligible endpoint preserves the existence of a complete deletion order. If a desired last position differs from the position of $x$, deleting $x$ first also preserves that desired last position.

Feasible last positions form an interval

Induct on the remaining length. Length one is immediate. If neither end is eligible, deletion is impossible. If only one end is eligible, deleting it is forced.

If both ends are eligible, consider the two states obtained by deleting either end first. At length two, both positions are feasible. At length at least three, if complete deletion is possible, the exchange property lets us delete both endpoints first. The resulting nonempty middle sequence is also deletable. Its feasible last positions belong to both child states. By induction, the feasible sets of those children are intervals, and they overlap, so their union is an interval as well.

Finding its boundaries

Simulate deletions, preferring the left endpoint whenever it is eligible. This choice preserves every feasible last position strictly to its right. If the left endpoint is ineligible, deleting the right endpoint is forced. Thus this simulation leaves the rightmost feasible last position. Preferring the right endpoint instead leaves the leftmost feasible last position.

If a simulation gets stuck with more than one element, output -1. Otherwise, minimize $C(k)$ over the interval between the two resulting positions.

The remaining positions form an interval, and the remaining values form a consecutive integer interval. Maintain both pairs of boundaries to process each deletion in $O(1)$. Maintain prefix and suffix cost sums to evaluate candidates. The total complexity is $O(N)$ time and $O(N)$ space.

Every cost sum is at most $N\cdot10^9\leq2\cdot10^{14}$, so use 64-bit integers.

The supplied naive solution uses interval DP, considering either eligible endpoint as the first deletion. Processing by interval length and retaining only the previous length gives $O(N^2)$ time and $O(N)$ space.

Solution written by GPT