Blackslex and Showering

Idea

The elevator route is basically a path through the array. The cost is the sum of edge lengths between consecutive elements:

$$S = \sum_{i=1}^{n-1} |a_i-a_{i+1}|.$$

We may delete at most one element. Since deleting an endpoint removes one positive-or-zero edge, and deleting a middle element cannot increase the cost by triangle inequality, deleting one element is always at least as good as deleting none. So we can just find the best single deletion.

What changes when we delete something?

Most of the route does not care. If you delete $a_k$, only the neighbors around $k$ are affected.

If $k=1$, the edge $|a_1-a_2|$ disappears. The saving is:

$$|a_1-a_2|.$$

If $k=n$, the edge $|a_{n-1}-a_n|$ disappears. The saving is:

$$|a_{n-1}-a_n|.$$

For a middle index $2 \le k \le n-1$, the old local cost was:

$$|a_{k-1}-a_k| + |a_k-a_{k+1}|.$$

After deleting $a_k$, the path jumps directly from $a_{k-1}$ to $a_{k+1}$, so the new local cost is:

$$|a_{k-1}-a_{k+1}|.$$

Therefore the saving is:

$$|a_{k-1}-a_k| + |a_k-a_{k+1}| - |a_{k-1}-a_{k+1}|.$$

This is the entire problem. No DP shrine required, despite the tag trying to look important.

Algorithm

1. Compute the original total cost $S$.
2. Initialize best with the better endpoint deletion saving.
3. For every middle index $k$, compute its saving.
4. Maximize best.
5. Answer $S - best$.

Why this works

The total cost is a sum of adjacent differences. Deleting one element only affects the adjacent edges touching that element. Every other edge remains exactly the same.

So instead of recomputing the full array cost after every possible deletion, we compute how much each deletion saves compared to the original total $S$. The best deletion is simply the one with maximum savings.

For middle elements, we subtract the two old edges and add the new shortcut edge. For endpoints, there is no shortcut edge, just one removed edge.

The statement says to output a real number, but all values are integers, so printing an integer is perfectly fine.

Complexity

Each test case is processed in $O(n)$ time and $O(n)$ memory for the array. The total $n$ over all tests is bounded, so this easily fits.