Suffix Operations
Contest: Codeforces Round 688 (Div. 2)
Difficulty rating: 1400
Tags: constructive algorithms, implementation

Gildong has an interesting machine that has an array $$$a$$$ with $$$n$$$ integers. The machine supports two kinds of operations:

1. Increase all elements of a suffix of the array by $$$1$$$.
2. Decrease all elements of a suffix of the array by $$$1$$$.

A suffix is a subsegment (contiguous elements) of the array that contains $$$a_n$$$. In other words, for all $$$i$$$ where $$$a_i$$$ is included in the subsegment, all $$$a_j$$$'s where $$$i \lt j \le n$$$ must also be included in the subsegment.

Gildong wants to make all elements of $$$a$$$ equal — he will always do so using the minimum number of operations necessary. To make his life even easier, before Gildong starts using the machine, you have the option of changing one of the integers in the array to any other integer. You are allowed to leave the array unchanged. You want to minimize the number of operations Gildong performs. With your help, what is the minimum number of operations Gildong will perform?

Note that even if you change one of the integers in the array, you should not count that as one of the operations because Gildong did not perform it.

Input format:
Each test contains one or more test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$).

Each test case contains two lines. The first line of each test case consists of an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of elements of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers. The $$$i$$$-th integer is $$$a_i$$$ ($$$-5 \cdot 10^8 \le a_i \le 5 \cdot 10^8$$$).

It is guaranteed that the sum of $$$n$$$ in all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print one integer — the minimum number of operations Gildong has to perform in order to make all elements of the array equal.

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Note:
In the first case, all elements of the array are already equal. Therefore, we do not change any integer and Gildong will perform zero operations.

In the second case, we can set $$$a_3$$$ to be $$$0$$$, so that the array becomes $$$[-1,0,0]$$$. Now Gildong can use the $$$2$$$-nd operation once on the suffix starting at $$$a_2$$$, which means $$$a_2$$$ and $$$a_3$$$ are decreased by $$$1$$$, making all elements of the array $$$-1$$$.

In the third case, we can set $$$a_1$$$ to $$$96$$$, so that the array becomes $$$[96,96,97,95]$$$. Now Gildong needs to:

- Use the $$$2$$$-nd operation on the suffix starting at $$$a_3$$$ once, making the array $$$[96,96,96,94]$$$.
- Use the $$$1$$$-st operation on the suffix starting at $$$a_4$$$ $$$2$$$ times, making the array $$$[96,96,96,96]$$$.

In the fourth case, we can change the array into $$$[-3,-3,-2,1]$$$. Now Gildong needs to:

- Use the $$$2$$$-nd operation on the suffix starting at $$$a_4$$$ $$$3$$$ times, making the array $$$[-3,-3,-2,-2]$$$.
- Use the $$$2$$$-nd operation on the suffix starting at $$$a_3$$$ once, making the array $$$[-3,-3,-3,-3]$$$.

Example input:
7
2
1 1
3
-1 0 2
4
99 96 97 95
4
-3 -5 -2 1
6
1 4 3 2 4 1
5
5 0 0 0 5
9
-367741579 319422997 -415264583 -125558838 -300860379 420848004 294512916 -383235489 425814447

Example output:
0
1
3
4
6
5
2847372102

Editorial:
First, let's find the optimal strategy for Gildong to follow to make all elements of the array equal.
It's obvious that there is no need to perform any operation on the suffix starting at $$$a_1$$$, since that operation changes all the integers in the array. For $$$i=2$$$ to $$$n$$$, the only way for $$$a_i$$$ to have equal value to $$$a_{i-1}$$$ is to perform one of the operations on the suffix starting at $$$a_i$$$ $$$abs(a_i - a_{i-1})$$$ times. This is because all operations starting at other positions do not change the difference between $$$a_i$$$ and $$$a_{i-1}$$$. Therefore, the minimum number of operations Gildong has to perform is $$$\sum_{i=2}^{n}{abs(a_i - a_{i-1})}$$$.
How should we change one element so that we can minimize this value? Let's take care of some special cases first. The optimal way to change $$$a_1$$$ is to make it equal to $$$a_2$$$, and then the minimum number of operations Gildong has to perform is decreased by $$$abs(a_2 - a_1)$$$. Similarly, the optimal way to change $$$a_n$$$ is to make it equal to $$$a_{n-1}$$$, and then the minimum number of operations Gildong has to perform is decreased by $$$abs(a_n - a_{n-1})$$$.
For the rest of the elements, changing $$$a_i$$$ affects both $$$abs(a_i - a_{i-1})$$$ and $$$abs(a_{i+1} - a_i)$$$. Here, we need to observe an important fact: This value is minimized when $$$a_i$$$ is between $$$a_{i-1}$$$ and $$$a_{i+1}$$$, inclusive. Intuitively, if $$$a_{i-1} < a_i > a_{i+1}$$$, Gildong has to perform one or more $$$2$$$-nd operations on the suffix starting at $$$a_i$$$, and then one or more $$$1$$$-st operations on the suffix starting at $$$a_{i+1}$$$ to compensate for the extra $$$2$$$-nd operations. This applies to the scenario where $$$a_{i-1} > a_i < a_{i+1}$$$ as well. If $$$a_i$$$ is between $$$a_{i-1}$$$ and $$$a_{i+1}$$$, these additional operations are unnecessary. In fact, the number of operations is decreased from $$$abs(a_i - a_{i-1}) + abs(a_{i+1} - a_i)$$$ to $$$abs(a_{i+1} - a_{i-1})$$$.
Therefore, we can decrease the number of operations needed by:
$$$$$$ \max \begin{cases} abs(a_2 - a_1)\\ abs(a_n - a_{n-1})\\ \max_{i=2..n-1}{abs(a_i - a_{i-1}) + abs(a_{i+1} - a_i) - abs(a_{i+1} - a_{i-1})} \end{cases} $$$$$$
The answer is $$$x-y$$$ where $$$x$$$ is the minimum number of operations Gildong needs to perform on the initial array, and $$$y$$$ is the maximum number of operations we can decrease by changing exactly one element.
Time complexity: $$$\mathcal{O}(n)$$$.