Gildong has an interesting machine that has an array a with n integers. The machine…
- User
Gildong has an interesting machine that has an array a with n integers. The machine supports two kinds of operations:
- Increase all elements of a suffix of the array by 1.
- 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 < j ≤ 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
Each test contains one or more test cases. The first line contains the number of test cases t (1 ≤ t ≤ 1000).
Each test case contains two lines. The first line of each test case consists of an integer n (2 ≤ n ≤ 2 ⋅ 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 ⋅ 10^8 ≤ a_i ≤ 5 ⋅ 10^8).
It is guaranteed that the sum of n in all test cases does not exceed 2 ⋅ 10^5.
Output
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.
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
Output
0 1 3 4 6 5 2847372102
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].
Assistant
We need to find the minimum number of operations needed by Gildong to make all array elements equal, after optionally changing one element to any integer (or leaving unchanged). The operations are: increase or decrease a suffix by 1. This is essentially being able to adjust the array with operations on suffixes.
Let's think: The operation adds or subtracts 1 to all elements from some index i to n. This is similar to building the array from some base. There's known concept: With suffix increment/decrement operations, to make all elements equal, the minimal number of operations equals the sum of absolute differences of adjacent elements? Let's derive.
Given array a[1..n]. Operation: choose an index i, and add delta = +1 or -1 to all a_i...a_n. We can think of constructing a from a constant array or reducing to constant.
Let's denote target constant value x. For each position, we need to achieve a_i = x. The operations affect suffixes. This is reminiscent of difference array. Define d_i = a_i - a_{i+1} for i=1..n-1, and perhaps also d_n = a_n (since after operations we can think of constructing from zero?). Actually, consider the process: Starting from all zeros, can we achieve a given array using suffix increments? If we only had increment operations (increase by 1), we could only create non-decreasing sequences? Wait, we have both increase and decrease, so we can go up and down. But note: A suffix increment adds same amount to a suffix, which changes differences between consecutive elements only at the boundary of the suffix. Specifically, if we increment suffix starting at i, then for j < i, differences unchanged; for j = i-1, the difference a_{i-1} - a_i changes by -1 (since a_i increased, difference decreases by 1). For j = i, the difference a_i - a_{i+1} changes by +1? Actually, careful: The operation adds c (which is +1 or -1) to all indices from i to n. Then for any j:
- If j < i-1: a_j - a_{j+1} unchanged.
- If j = i-1: then a_{i-1} - (a_i + c) = (a_{i-1} - a_i) - c.
- If j >= i: a_j + c - (a_{j+1}+c) = a_j - a_{j+1} unchanged.
Thus only the difference at position i-1 (if i>1) changes by -c. Also the last element a_n gets changed, but it's not part of a difference. So operations affect exactly one difference (the one left of the start index) by the opposite of the amount added. So the problem of making all elements equal to x can be translated into adjusting differences.
Consider we want final array all equal to x. Equivalent to start with array a, apply operations to transform into array where all values = x. Alternatively, think about the array b_i = a_i - x. Then we want to make all b_i zero. Operations on suffixes: adding +1 or -1 to suffix of b (since adding to a is same). Now consider differences of b: b_i - b_{i+1} = (a_i - x) - (a_{i+1} - x) = a_i - a_{i+1} = original diff. So diff_i = a_i - a_{i+1}. When we apply operation on suffix from i with delta d (d = +1 or -1), diff_{i-1} changes by -d (if i>1), and no other diffs change. So we can adjust each diff individually? Starting from original diff array d_1, d_2, ..., d_{n-1}. To get to all zeros b_i=0, the final differences must be zero. So we need to transform each diff_i to zero. Each operation can change one diff (specifically diff_{i-1}) by -d. So we can adjust diff_{i-1} up or down by unit steps.
But there's a catch: The operations also affect the last element b_n directly, but that's captured by the cumulative sum of diffs? Actually, if we adjust diff values to zero, then b_1 must equal b_2 = ... = b_n. Then to make them all zero we also need to adjust the common offset? However, note that if we set all diffs to zero, then the array b becomes constant, but that constant might not be zero; we would then need to add a global constant to all elements? But operations only affect suffixes, not prefixes. Let's check: If we apply operation on suffix starting at index 1, that adds delta to all elements. That changes the whole array by delta. That operation corresponds to changing which diff? For i=1, there is no diff_{0}. Actually, operation on i=1 adds delta to all elements, so all b_j shift by delta. This doesn't affect any diff because it's uniform shift. So after making diffs zero, we can apply operation on suffix starting at 1 to adjust the common value to zero. That operation is counted. So we can adjust the constant separately.
Alternatively, we can think in terms of constructing b from zero using suffix operations. Starting from all zeros, we want to get to b. The minimal number of operations is known to be sum over i=1..n-1 of max(0, b_i - b_{i+1})? Not exactly. Let's derive minimal ops to turn zeros into b using suffix increments/decrements.
Let’s consider process reversed: We start from b and want to get to zeros. Operation: choose i and add delta to suffix. That's like we can reduce the array to zeros by adjusting. Equivalent to typical problem: "minimum number of operations of increasing/decreasing suffix by 1 to zero out array". This is similar to "make array zero" problem with range increments. Known result: The minimum number of operations = sum_{i=1}^{n} |delta_i| where delta_i is something like prefix sums? Let's think differently.
Define c_i = b_i - b_{i+1} for i=1..n-1, and let s = b_n (the last element). Because the operation at index i (i>=2) changes only c_{i-1} by -delta. The operation at i=1 changes the whole array. So we can treat adjusting c's and then adjust the base.
We can simulate: Suppose we first aim to make all b_i equal. That is, we want to zero out all differences. The operations that affect suffix i>=2 can adjust c_{i-1}. Essentially, we need to make c_i = 0 for all i. Starting from c_i = a_i - a_{i+1}. Each operation at index i+1 with delta d changes c_i by -d. So we can adjust each c_i independently? Not exactly, because adjusting c_i via operation at i+1 does not affect other c's, but it does affect the overall sum? Actually, it also changes b_n? Let's see: Operation at index j adds d to all b_i for i>=j. That changes b_n by d. So if we use operations at indices >1, they also change b_n. But that's fine because b_n is part of the constant later. So we can treat each c_i adjustment as separate, with the effect that each operation at position i+1 also adds d to the cumulative offset of all elements from i+1 onward. But when we later adjust the constant via operation at index 1, that can offset any leftover b_n.
Thus the minimal number of operations to zero out b (make all zeros) is: sum_{i=1}^{n-1} |c_i| plus |b_1|? Let's test on small examples.
Take a = [1,1]. Then b = [1,1] if x=1? Actually for target x=1, b=0,0. But we need to consider that we can choose x. But first consider for a given target, number of ops. The problem: we can choose x to minimize ops.
We have ability to change one element arbitrarily before operations.
We need to compute minimal ops across all choices of x and possibly one element change.
Alternatively, we can think about the effect of operations on differences directly.
Observation: After all operations, all elements become some value x. Let’s denote final value x. The operations performed correspond to a sequence of suffix increments/decrements. Consider the net effect on each position: Let delta_i be the total amount added to suffix starting at i. More precisely, define an array ops[1..n], where ops[i] is the net change (could be positive or negative) applied to suffix starting at i (i.e., we performed ops[i] times operation type 1 and negative ops[i] times type 2? But careful: operations are unit +1 or -1 on a suffix. So net effect can be integer, can be positive, negative, or zero. Let f_i be the cumulative net addition to index i from all operations. Because an operation on suffix j affects index i if i >= j. So f_i = sum_{j=1}^{i} ops[j]? Actually, if we define op[j] as the net delta applied to suffix starting at j (i.e., we add op[j] to all elements from j to n). Then the total addition to element i is sum_{j=1}^{i} op[j]? Because any operation on suffix j with start <= i will affect i. But careful: operation on suffix j adds to all indices >= j. So for a given index i, it is affected by all ops[j] where j <= i. So f_i = sum_{j=1}^{i} op[j]. Yes.
We start from initial a_i. After operations, we have final a_i + f_i = x for all i. So f_i = x - a_i. So we have for i=1..n: sum_{j=1}^{i} op[j] = x - a_i.
Let’s denote prefix sums of op: P_i = sum_{j=1}^{i} op[j] = x - a_i.
We have P_n = x - a_n. Also P_i = x - a_i. Then difference: P_i - P_{i-1} = op[i] = (x - a_i) - (x - a_{i-1}) = a_{i-1} - a_i. So op[i] = a_{i-1} - a_i, for i>=2. And op[1] = P_1 = x - a_1.
So interestingly, given target x, the necessary op[i] are forced: For i >= 2, op[i] must equal a_{i-1} - a_i. For i=1, op[1] = x - a_1. That means the operations are determined uniquely by x. Because if we require final array all equal to x, the only way to achieve it is to apply exactly those net operations. Check: Starting with a, we need to apply op[1] to suffix 1 (i.e., add op[1] to all elements), then op[2] to suffix 2, etc. Indeed, the resulting array: after applying these net ops, element i gets sum_{j=1}^{i} op[j] = (x - a_1) + sum_{j=2}^{i} (a_{j-1} - a_j) = (x - a_1) + (a_1 - a_i) = x - a_i. Wait: sum_{j=2}^{i} (a_{j-1} - a_j) telescopes to a_1 - a_i. So total = (x - a_1) + (a_1 - a_i) = x - a_i. So adding that to a_i yields x. So yes, that works.
Now note: op[i] for i>=2 are fixed regardless of x! Only op[1] depends on x. So the total number of operations (the count, not net sum) needed is sum_{i=1}^{n} |op[i]|. But careful: each operation is a unit increment or decrement of a suffix. Since we can apply net op[i] by doing |op[i]| operations of appropriate sign. The minimal number of operations to achieve the net amounts is exactly the sum of absolute values of op[i] because we can do each unit operation independently (there is no interference that would reduce count). Since the op[i] are independent (they are applied to different suffixes, but even if same suffix used multiple times, they combine), we need to perform exactly |op[1]| operations on suffix 1 (each +/-1), and for each i>=2, |op[i]| operations on suffix i. There is no way to achieve same net effect with fewer total ops because each op[i] corresponds to adjusting a specific difference. So the minimal number of operations for a given target x is: |x - a_1| + sum_{i=2}^{n} |a_{i-1} - a_i|.
Because op[1] = x - a_1, and for i>=2, op[i] = a_{i-1} - a_i. Note that op[i] for i>=2 are independent of x. So the total ops = |x - a_1| + constant, where constant = sum_{i=2}^{n} |a_{i-1} - a_i|.
But wait, is that always correct? Let's test with provided examples.
Example 1: n=2, a=[1,1]. Then constant = |1-1|=0. So total ops = |x-1| + 0. To minimize, choose x=1 => 0. Output 0. matches.
Example 2: a = [-1,0,2]. Constant = |(-1)-0| + |0-2| = 1+2=3. So total ops = |x - (-1)| + 3 = |x+1|+3. But note answer after optional change is 1. Our formula yields minimal possible ops without change is min_x (|x+1|+3) = 3 (choose x = -1). But the sample says answer 1 after we change one element. So our formula for original array would give 3, but they got 1 after change. So that seems consistent: without change, answer would be 3? But the problem says we can change one element arbitrarily. So we need to incorporate that.
Now note: Changing one element to any value will affect both the constant sum and possibly the first term? Because the formula uses a_1 and differences. If we change a_k to some new value v, the array changes. Then the minimal ops for that modified array (with target x) becomes |x - a'1| + sum{i=2}^{n} |a'{i-1} - a'i|. Since we can choose both the changed index and value, we want to minimize the resulting minimal ops: min{k, v} ( min_x ( |x - a'1| + sum{i=2}^{n} |a'{i-1} - a'_i| ) ). And we can also choose not to change.
Since the inner minimization over x is easy: For any array, the minimal total ops is simply constant + min_x |x - a'1|, and min_x |x - a'1| = 0 by choosing x = a'1. So actually, the best target x is always a'1. Because the term |x - a'1| can be made zero by setting x = a'1. Wait, check: If we choose x = a'1, then the total ops = 0 + sum{i=2}^{n} |a'{i-1} - a'i|. So the minimal ops for given array is simply the sum of absolute differences between consecutive elements. Because we can set target equal to the first element (after operations, all become a'1). So the number of operations needed is sum{i=2}^{n} |a'{i-1} - a'i|. Is that always valid? Let's verify with our earlier derivation: total ops = |x - a_1| + sum{i=2}^{n} |a{i-1} - a_i|. If we set x = a_1, then ops = sum{i=2}^{n} |a{i-1} - a_i|. Indeed, that seems minimal because the first term is non-negative. So the optimal target is always the original first element (if we don't change). But note: Could there be a scenario where choosing x not equal to a_1 reduces the sum of differences? No, because the sum of differences is independent of x. So it's clearly optimal to set x = a_1 to eliminate the first term. So the minimal number of operations for an array a is S(a) = sum{i=2}^{n} |a{i-1} - a_i|.
But wait: In example 2 without change, S(a) = |(-1)-0| + |0-2| = 1+2=3, which matches earlier derived minimal ops =3. So answer without change would be 3. But after change, we can get 1 as per sample.
So the problem reduces to: Given array a, we can modify one element to any value to minimize the sum of absolute differences of consecutive elements. Then answer = that minimized sum. Because after changing, Gildong will perform operations count = S(a').
But is it always optimal to choose target x = a'_1? Let's test: If we change some element, a'_1 might change if we modify index 1. Then indeed we can set x = a'1. But could it be better to choose a different target? Let's consider array a' after change. According to formula total ops = |x - a'1| + sum{i=2}^{n} |a'{i-1} - a'_i|. The sum term is fixed for given a'. Minimizing over x gives x = a'_1. So the minimal ops for that a' is indeed sum of differences. So yes.
Thus the problem: We can change one element a_k to any real (integer) value to minimize the sum of absolute differences. We need to output that minimum possible sum.
But wait: The sample case 4: a = [-3 -5 -2 1]. Compute differences: |(-3)-(-5)|=2, |(-5)-(-2)|=3, |(-2)-1|=3, total = 8. But answer after change is 4. So by changing one element we can reduce sum to 4. Let's check: They changed to [-3,-3,-2,1] maybe? Actually note they changed array into [-3,-3,-2,1] by presumably changing a_2 from -5 to -3. Then differences: |-3 - (-3)|=0, |-3 - (-2)|=1, |-2 - 1|=3, sum=4. That's indeed answer. So our derived logic matches: answer = minimized sum of absolute differences after one modification.
Now note: The operations count computed in sample matches: For changed array, S=4.
Thus problem reduces to: Given array a[1..n], we can change at most one element (or zero) to any integer value. We need to minimize the sum of absolute differences between consecutive elements. That is, we want to choose index p and value v to minimize:
S' = sum_{i=2}^{n} |a_{i-1}' - a_i'|, where a_j' = a_j for j != p, and a_p' = v.
We want min_{p, v} S'.
This is a classic problem: minimize the sum of absolute differences by changing one element.
We need to compute efficiently for n up to 2e5, sum n up to 2e5, t up to 1000.
We can compute original sum S0 = sum_{i=2}^{n} |a_i - a_{i-1}|.
If we change a_p, which differences are affected? Only the differences involving p: i.e., if p > 1, then |a_{p-1} - a_p| changes to |a_{p-1} - v|; if p < n, then |a_p - a_{p+1}| changes to |v - a_{p+1}|. All other differences remain the same. So S' = S0 - (original contributions of edges incident to p) + (new contributions with v).
Specifically, for p:
- If p=1: only the difference to a_2 is affected: originally d1 = |a_1 - a_2|. After change, becomes |v - a_2|. So S' = S0 - d1 + |v - a_2|.
- If p=n: only difference with a_{n-1}: S' = S0 - |a_{n-1} - a_n| + |a_{n-1} - v|.
- For 1<p<n: S' = S0 - (|a_{p-1} - a_p| + |a_p - a_{p+1}|) + (|a_{p-1} - v| + |v - a_{p+1}|).
Thus for each p, we can try to choose v to minimize new contributions. The best v is something that minimizes |a_{p-1} - v| + |v - a_{p+1}| (if both neighbors exist) or just |v - a_2| for p=1, etc. For interior p, the expression f(v) = |L - v| + |v - R|, where L = a_{p-1}, R = a_{p+1}. That is minimized when v is any value between L and R (inclusive), and the minimal value is |L - R|. If L <= R, then for v in [L,R], f(v)=R-L; else if L > R, then for v in [R,L], f(v)=L-R. So the minimal sum = |L - R|.
For endpoints, f(v) = |v - R| (with R = a_2 or a_{n-1}) is minimized when v = R, giving 0. So we can reduce the incident contributions to zero for endpoints by setting v equal to the neighbor.
Thus, we can compute the reduction possible at each position:
- For p=1: original contribution C1 = |a_1 - a_2|. After optimal change, new contribution = 0 (choose v = a_2). So reduction = C1.
- For p=n: reduction = |a_{n-1} - a_n|.
- For interior p: original contribution = |a_{p-1} - a_p| + |a_p - a_{p+1}|. After optimal change, we can get new contribution = |a_{p-1} - a_{p+1}|. So reduction = (|a_{p-1} - a_p| + |a_p - a_{p+1}|) - |a_{p-1} - a_{p+1}|.
So overall minimal S' = S0 - max_possible_reduction, where reduction = max over p of these possible reductions. Because we can only change one element, we want to maximize the reduction. But note: Could there be a scenario where the optimal v is not exactly the one that minimizes the two-edge sum? For interior, the minimal sum is indeed |L - R|, which is achieved for any v between L and R. So yes. But we need to ensure that v can be any integer? The problem allows to change to any integer. So we can achieve that. For endpoints, we can set v = neighbor to get 0, also integer. So maximum reduction is as above.
But is there any other effect? Could changing a value affect more than two differences? No, only adjacent differences. So reduction is limited to those two.
Thus answer = S0 - max_reduction, where max_reduction = max( reduction_1, reduction_n, and for i=2..n-1, reduction_i = |a_{i-1} - a_i| + |a_i - a_{i+1}| - |a_{i-1} - a_{i+1}| ).
However, we must also consider the possibility of not changing any element, which yields S0. That's automatically considered because we subtract max reduction; if max reduction is 0, then S0 remains.
But is it possible that after change, the optimal target x might not be a'_1? Wait, we argued that minimal ops = sum of differences for that array. But we derived that by setting target equal to a'_1. Could there be a scenario where after changing an element, the sum of differences is minimized by choosing a different target x, but then the first term |x - a'_1| becomes non-zero, potentially reducing sum of differences? Actually, the sum of differences is independent of x. The total ops = |x - a'_1| + sum_diff. To minimize, we set x = a'_1, making first term zero. So sum_diff is the minimal achievable. So indeed, after change, the optimal operations count is exactly the sum of absolute differences. So we only need to minimize sum_diff.
But careful: The above derivation assumed that we can choose the target x arbitrarily. But is there any constraint that final array elements must be equal to some integer? Not specified; they can be any integers because operations change by ±1 each, starting with integer array, so final x will be integer if we use integer number of operations. Since we are allowed to choose x arbitrarily, we can choose integer equal to a'_1. So yes.
Thus answer is S0 - D, where D = max possible reduction.
Now we must compute D.
But wait: The sample test cases:
Example 2: a = [-1,0,2]. S0 = 1+2=3. Reduction options: p=1: | -1 - 0 | =1 p=2: | -1-0| + |0-2| - | -1-2| = 1+2 - 3 =0? Actually | -1-2| =3, so reduction=0. p=3: |0-2| =2. Max reduction = max(1,0,2)=2. Then S0 - D = 3-2=1. Matches sample (they got 1). They changed a_3 to 0 (p=3) giving reduction of 2? Actually changing a_3 to 0 reduces |0-2| from 2 to |0-0|=0, reduction 2. So yes.
Example 3: n=4, a=[99,96,97,95]. S0 = |99-96|+|96-97|+|97-95| = 3+1+2=6? Wait compute: 99-96=3, |96-97|=1, |97-95|=2 => total 6. But sample answer is 3. So reduction must be 3. Let's compute reductions: p=1: |99-96| =3, reduction=3. p=2: |99-96|+|96-97| - |99-97| = 3+1 - 2 =2. p=3: |96-97|+|97-95| - |96-95| = 1+2 - 1 =2. p=4: |97-95| =2, reduction=2. Max reduction = 3, S0-3=3, matches.
Example 4: [-3,-5,-2,1] S0 = 2+3+3=8. Reductions: p1: | -3 - (-5) | =2 p2: | -3 - (-5)| + | -5 - (-2)| - | -3 - (-2)| = 2+3 - 1 =4? Actually | -3 - (-2) | = 1, yes reduction=4. p3: | -5 - (-2)| + | -2 - 1| - | -5 - 1| = 3+3 - 6 =0? Wait | -5 - 1| =6, reduction=0. p4: | -2 - 1| =3, reduction=3. Max reduction =4, S0-4=4, matches answer.
Example 5: [1,4,3,2,4,1] S0 compute: |1-4|=3, |4-3|=1, |3-2|=1, |2-4|=2, |4-1|=3 => total 10? Actually 3+1+1+2+3=10. Sample output is 6. So reduction must be 4. Let's compute reductions: p1: |1-4|=3 -> reduction 3 p2: |1-4|+|4-3| - |1-3| = 3+1 - 2 =2? |1-3|=2, so 2. p3: |4-3|+|3-2| - |4-2| = 1+1 - 2 =0. p4: |3-2|+|2-4| - |3-4| = 1+2 - 1 =2. p5: |2-4|+|4-1| - |2-1| = 2+3 - 1 =4? |2-1|=1 -> 2+3-1=4. p6: |4-1|=3 -> reduction 3. Max reduction = 4, S0-4=6 matches.
Example 6: [5,0,0,0,5] S0: |5-0|=5, |0-0|=0, |0-0|=0, |0-5|=5 => total 10. Sample output 5. Reductions: p1: |5-0|=5 p2: |5-0|+|0-0| - |5-0| =5+0-5=0? Actually |5-0|=5, so 5+0-5=0. p3: |0-0|+|0-0| - |0-0| =0+0-0=0. p4: |0-0|+|0-5| - |0-5| =0+5-5=0. p5: |0-5|=5 Max reduction =5, S0-5=5 matches.
Example 7: large numbers, we'll trust.
Thus formula holds.
Now we must compute S0 and max reduction efficiently.
Edge Cases:
-
n=2: Only p=1 and p=2. For p=1, reduction = |a1 - a2|; p=2 reduction = |a1 - a2|; also interior? There is none. So max reduction = |a1 - a2|. Then answer = S0 - max = |a1-a2| - |a1-a2| = 0. But wait, with n=2, can we always make ops zero? Let's test: array [1,2]. S0 = 1. Reduction =1, answer =0. Is it possible? If we change one element to match the other, then array becomes [1,1] or [2,2], sum diff =0. Yes, Gildong then needs 0 ops. So answer 0. But what if we don't change? then answer =1. But we can change, so answer 0. That matches formula. Good.
-
But consider n=2, a=[1,1] -> S0=0, reduction=0, answer=0.
-
n=2, a=[1000000000, -1000000000] => S0=2000000000, reduction=2000000000, answer=0. Yes.
Now, what about changing the element to a value that is not between L and R? For interior p, the minimal sum of two absolute differences is |L-R|, achieved when v is between L and R. Could we achieve a reduction larger than the formula by also affecting other differences? No.
Thus answer seems straightforward: compute sum of absolute differences; compute for each interior index i the reduction as described, plus endpoints; take maximum reduction; subtract from sum.
But wait: is there any catch regarding the ability to change to any integer? Possibly the optimal v for interior p is indeed any value in the interval. But what about the possibility of also changing the first element to something else that might affect the sum of differences? That is covered.
Now, we should double-check the reasoning that the minimal number of operations is sum of absolute differences after change. Let's derive more formally: We have array a. The operations are suffix increments/decrements. It is known that the minimal number of operations to make all equal is the total variation (sum of absolute differences) because we can think of constructing from first element. Actually, there is known problem: "Make array equal with suffix increment operations" - the answer is sum of positive differences? But we have both increase and decrease. Let's do a constructive argument: Starting with a_1, we want all subsequent to equal a_1. For each i from 2 to n, to make a_i equal to a_1, we can apply suffix at i with delta = a_1 - a_i? But careful: When we adjust later indices, we affect earlier ones? Actually, if we apply operation on suffix i, it changes a_i,...,a_n. If we set them sequentially: to fix a_2, we apply suffix 2 with delta = a_1 - a_2. Then a_2 becomes a_1, but a_3..a_n also change. Then to fix a_3, we may need to adjust further, and the total number of operations would be sum of absolute differences? Let's simulate: a = [x, y, z]. Start: [x,y,z]. Goal: all equal to x. Operation on suffix 2: add (x - y). Then array becomes [x, x, z + (x - y)]. Next, operation on suffix 3: add (x - (z + x - y)) = y - z. So total ops = |x-y| + |y-z|. Indeed matches sum of abs diffs. But if we had also decreased some? The signs work out. So that algorithm yields exactly sum of absolute differences. Also we could start with any target but minimal is achieved by target = a_1? Could target = a_n be better? That would give sum of abs diffs in reverse? Actually, the sum of absolute differences is independent of direction? For a given target x, the necessary ops is |x-a_1| + sum_{i=2}^n |a_{i-1} - a_i|. The sum term doesn't depend on x. So minimal is at x = a_1, giving sum diffs. So indeed it's consistent.
Thus answer = minimize sum of absolute differences after one change.
Now, is it always optimal to change exactly one element? Possibly we might not change any if it's already optimal. That's captured by D=0.
So problem reduces to: given array a, compute S = sum_{i=2}^{n} |a_i - a_{i-1}|, and D = max_{i} delta_i, where for i=1: delta_i = |a_1 - a_2|; for i=n: delta_i = |a_{n-1} - a_n|; for others: delta_i = |a_{i-1} - a_i| + |a_i - a_{i+1}| - |a_{i-1} - a_{i+1}|. Then answer = S - D.
But wait, we must consider also the possibility of changing an element to a value that does not achieve the optimal reduction for that position? No, we choose v optimally.
But is there any scenario where changing an element might produce a sum of differences that is less than S - max(delta_i)? Could changing two edges simultaneously with one change reduce more than delta_i? That's exactly what we computed: the reduction from changing a_i is at most that delta_i. So max reduction is best possible.
We must ensure no other effect like if we change a value, maybe the optimal target x could be different and lead to further reduction? But as argued, the number of operations for final array is exactly sum of abs diffs, regardless of target because we can set target equal to first element. However, is there any situation where after change, the sum of abs diffs is not the minimal operations count? Let's re-express: For a given array a', the minimal number of operations is min_x (|x - a'1| + sum{i=2}^n |a'{i-1} - a'i|). The min over x is sum{i=2}^n |a'{i-1} - a'_i| because we can set x = a'_1. So it's exactly that sum. So no further optimization.
Thus answer is S - D.
Now we must compute D efficiently. Straightforward O(n) per test case. S = sum |a_i - a_{i-1}|.
But caution: The reduction for interior i: |a_{i-1} - a_i| + |a_i - a_{i+1}| - |a_{i-1} - a_{i+1}|. This is always >=0 because of triangle inequality: |a_{i-1} - a_i| + |a_i - a_{i+1}| >= |a_{i-1} - a_{i+1}|. So reduction >=0. For endpoints, reduction is just the incident difference, non-negative.
Now, is there any possibility that by changing an element we can achieve reduction > that? What if we change a_i such that the new value v also affects the first term if we set x = a'_1? But we already accounted that the total ops = sum diffs. But maybe there is a scenario where after change, we can set x to something else to reduce the sum diffs? No, sum diffs is fixed for that array, independent of x. So no.
Thus algorithm is clear.
Now we need to implement and test on sample.
However, look at sample 7: output is 2847372102. Our formula should yield that.
Now, are there any pitfalls? The array values can be large: up to 5e8, differences up to 1e9, sum up to maybe 2e5*1e9=2e14, which fits in 64-bit (max about 9e18). So use long long.
Now, we need to handle t test cases, sum n <= 2e5.
Now, check for edge cases: n=2 works. n=3, we computed.
Potential nuance: Could we consider changing a value to something that yields a sum of differences that is lower than S - max(delta_i) because we might also affect the ability to set target x = a'_1? For example, if we change a_1, then sum diffs might be minimal, but also we could set x to something else to reduce the first term? But sum diffs is independent. However, the total ops formula is |x - a'_1| + sum_diffs. If we set x = a'_1, we get sum_diffs. Could there be a case where sum_diffs is larger, but we can choose x not equal a'_1 such that the sum |x - a'_1| + sum_diffs is smaller than the min over x after some other change? But that's exactly the expression we already minimized over x. For a given array, the minimal ops is min_x (|x-a'_1|+sum_diffs) = sum_diffs because we set x = a'_1 gives sum_diffs. So it's exactly sum_diffs.
But what about the possibility that after change, the minimal over x might be less than sum_diffs? That would require the term |x-a'_1| to be negative? No, it's non-negative, so sum_diffs is a lower bound. So minimal is exactly sum_diffs.
Thus all good.
Now, wait: The original reasoning that op[i] = a_{i-1} - a_i for i>=2 is based on the equations derived from target x. But we concluded that for any array, the minimal ops to get all equal is sum of absolute differences. That is a known result. Let's double-check with a custom case: a = [0, 1, 0]. S = |0-1|+|1-0|=1+1=2. Can we do it in 2? Try to make all equal to 0 (target = a1=0). Use suffix at 2: add -1 to indices 2,3 => [0,0,-1]. Then suffix at 3: add +1 => [0,0,0]. 2 ops. Yes.
What about target = 1? Then ops would be |1-0| + sum diffs = 1+2=3. So 2 is min.
Thus correct.
Now, ensure that after changing one element, the answer remains sum of diffs.
Now, is there any scenario where we might want to change a value such that the new a'_1 is not the target? But we can choose target accordingly. So it's fine.
Thus solution: compute S and reductions.
Now, let's verify with sample 7 manually maybe? Not needed.
Now, code: For each test case, read n, array a (list of ints). Compute diffs array maybe? Actually, we can compute S as we go. Then for i from 0 to n-1 (0-indexed), we compute reduction:
- i=0: reduction = abs(a[0]-a[1])
- i=n-1: reduction = abs(a[n-2]-a[n-1])
- else: reduction = abs(a[i-1]-a[i]) + abs(a[i]-a[i+1]) - abs(a[i-1]-a[i+1])
Take max_reduction. Answer = S - max_reduction.
But note: S includes both diffs for i=0 and i=n-1? Actually S = sum_{i=1..n-1} |a_i - a_{i-1}|. So includes those edges.
Implementation: Compute an array diff where diff[i] = |a[i+1]-a[i]| for i=0..n-2. Then S = sum diff.
Then for i from 0 to n-1 (positions), if i==0: reduction = diff[0]; if i==n-1: reduction = diff[n-2]; else: reduction = diff[i-1] + diff[i] - |a[i-1] - a[i+1]| (note: diff[i-1] is |a[i-1]-a[i]|, diff[i] is |a[i]-a[i+1]|). So compute.
But careful: For i=1 (second element, 0-indexed i=1): diff[i-1] = diff[0] = |a[0]-a[1]|, diff[i] = |a[1]-a[2]|, and we need |a[0]-a[2]|.
Ok.
Complexity O(n) per test.
Now, confirm with n=2: diff array of size 1: diff[0]=|a0-a1|. Then i=0: reduction = diff[0]; i=1: reduction = diff[0]; max reduction = diff[0]; S = diff[0]; answer = 0. Good.
Now, check n=3: diff[0]=|a0-a1|, diff[1]=|a1-a2|. S= diff0+diff1. i=0: reduction=diff0; i=1: reduction = diff0+diff1 - |a0-a2|; i=2: reduction=diff1. max_reduction. Works.
Now, one more nuance: The option to change an element to any integer, but we are assuming we can achieve the minimal new contributions exactly. For interior, we need v between L and R to achieve new contribution = |L-R|. Is it always possible to pick integer v between L and R? Yes, if L <= R, we can pick any integer in between; if L and R are integers, the interval [L,R] contains integers, including L and R themselves. Similarly if L > R, interval [R,L] contains integers. So possible.
For endpoint, we need v = neighbor (integer) to achieve 0, obviously integer.
Thus achievable.
Now, verify with large numbers and negative values: intervals work fine.
Now, is there any scenario where the optimal v is not between L and R but some other value yields same sum? Actually, the function f(v)=|L-v|+|v-R| is minimized on the entire closed interval between L and R, giving constant value |L-R|. For v outside, it's larger. So it's okay.
Thus solution stands.
Now, I'll double-check the derivation from operations to sum of differences. Actually, we derived that minimal ops = sum |a_i - a_{i-1}| (for i>=2). Let's confirm with another example: a = [5,0,0,0,5] from sample. Without change, S = 10. Is it possible to do in 10 ops? Let's try to make all equal to first element 5. Process: to set index2 from 0 to 5, suffix 2 add +5 => array: [5,5,5,5,10]. Then to set index5 from 10 to 5, suffix5 add -5 => [5,5,5,5,5]. That's 5+5=10 ops. Yes. Alternatively, could we do less? Maybe if we choose target 0? Then first term |0-5|=5, plus sum diffs =10? Actually sum diffs is still 10, total 15. So 10 is min.
Now after change, we can reduce S to 5, e.g., change last element to 0 -> array [5,0,0,0,0], S = |5-0| + 0+0+0 =5. Then operations: target =5? Actually we set target = a1 =5, then we need to change index2 from 0 to5, which requires suffix2 +5 => array becomes [5,5,5,5,5]? Wait after changing, array is [5,0,0,0,0]. To make all 5: suffix2 add +5 => [5,5,5,5,5] -> 5 ops. That's 5 ops. Good.
Now, check if there is any alternative where we could achieve even fewer ops by targeting a different value. If target =0, then need to change first element from 5 to 0: suffix1 add -5 => [-? Actually suffix1 adds to all, so applying -5 yields [0,-5,-5,-5,-5] -> then need to fix others? Not simpler. So yes, 5 is min.
Thus answer matches.
Now, we must ensure to output the answer as an integer (64-bit). Good.
Now, think about potential pitfalls: The problem says we can change one integer to any other integer. That includes possibly making it huge, but we consider optimal.
Now, consider edge case n=1? But constraints n>=2, so fine.
Now, think about potential overflow: S can be up to (n-1)*1e9 ~ 2e14, fits in 64-bit signed (9e18). For reduction calculation, we compute differences, all within 64-bit. So use long long.
Now, implementation: read t, loop, for each test: read n, read array a (vector). Compute diff vector (size n-1). Compute S. Then compute max_reduction = 0 (or use long long). For i from 0 to n-1: if i==0: red = diff[0]; if i==n-1: red = diff[n-2]; else: red = diff[i-1] + diff[i] - abs(a[i-1] - a[i+1]); update max. Then answer = S - max_reduction. Print answer.
But careful: For n=2, diff.size() =1, we need to handle i=0 and i=1. i=0 uses diff[0]; i=1 uses diff[0] as well. That's fine. But when n=2, diff[n-2] = diff[0], okay.
But we need to ensure we don't access out-of-bounds for i-1, i+1 when n=2 for interior case? For n=2, we never go into else because i=0 and i=1 are endpoints. So we skip else. Good.
Now, test with sample:
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
Compute for last one? We'll trust.
Now, implement.
But before finalizing, we should double-check the reasoning more thoroughly because sometimes in problems like this, the minimal operations might be sum of positive differences only, but we have both signs. Let's confirm with a non-monotonic array.
Consider a = [2, 1, 2]. S = |2-1|+|1-2| = 1+1=2. Can we achieve 2 ops? Target = 2 (a1). Steps: suffix2 add +1 => [2,2,3]. Then suffix3 add -1 => [2,2,2]. 2 ops. Yes. Could we do in 1? Possibly? Try to set target =1. Then need to change first from2 to1: suffix1 add -1 => [1,0,1]; then need to fix second? Not 1. So 2 is min.
Now, after changing maybe we could do better.
All good.
But wait, there is known variant: with operation "increase/decrease suffix by 1", the minimal number to make all elements equal is sum of absolute differences between consecutive elements. This is similar to making array constant by adjusting differences, indeed.
Now, confirm with negative numbers: a = [-5, -3, -4]. S = 2+1=3. Target = -5? Apply suffix2 add -2 => [-5,-5,-6]; suffix3 add +1 => [-5,-5,-5]. 3 ops. Good.
Now, everything aligns.
Thus answer is straightforward.
Now, we must produce code accordingly.
However, let's think: Could there be any scenario where changing a value to a non-optimal v yields a reduction even larger? For interior, we derived minimal new contribution is |L-R|. Could we achieve reduction > (|L-a_i|+|a_i-R| - |L-R|)? Actually reduction = old - new. Since new minimal is |L-R|, reduction max is old - |L-R|, as we used. So no.
But what about the endpoints? New contribution minimal is 0, reduction = old. So that's max.
Thus correct.
Now, need to handle potential issue: After we change a value, the sum of differences changes, but also the target might be chosen differently, but we already accounted that optimal target yields sum diffs as total ops. Could there be scenario where after change, the sum of differences is not minimal? Wait, we minimize over change and then over operations. But we fixed the operation count to be sum diffs after change. But is it possible that after change, there is a way to achieve all equal with fewer operations than sum diffs? Let's try to find a counterexample.
Suppose after change, the array becomes such that the sum of absolute differences is D', but perhaps we can use a different sequence of suffix operations that yields all equal with less than D' operations? Our earlier derivation showed that for any array, the minimal operations = min_x (|x - a_1| + sum_{i=2}^{n} |a_{i-1} - a_i|) = sum_{i=2}^{n} |a_{i-1} - a_i| because we can set x = a_1. This seems to be a lower bound? Could there be a strategy that mixes operations to achieve the goal with fewer than sum diffs? Let's prove minimal.
We have derived that given any sequence of operations, the net changes op[i] must satisfy op[1] = x - a_1 and op[i] = a_{i-1} - a_i for i>=2, where x is final constant. But that derivation assumed we end up with all equal to x. However, is it necessarily true that any sequence of operations results in net ops that satisfy op[i] = a_{i-1} - a_i? Wait, we derived that if we want final array constant x, then the net effects f_i = sum_{j=1}^i op[j] = x - a_i. This is a necessary condition. And from that we solved op[i] = f_i - f_{i-1} = (x - a_i) - (x - a_{i-1}) = a_{i-1} - a_i for i>=2, and op[1] = f_1 = x - a_1. So any successful sequence must have exactly those net op values. But could there be a sequence that uses fewer operations because some ops cancel? The net op[i] is the algebraic sum of increments applied to suffix i. The total number of operations is sum_i |op[i]| if we consider each unit operation independently. But could we achieve the net op[i] with fewer than |op[i]| operations? No, because each operation changes op[i] by ±1 for the chosen suffix. To achieve a net integer op[i], we need at least |op[i]| operations on that suffix (since each operation changes it by 1 in one direction). However, could we combine operations on different suffixes to achieve the same net effect with fewer total operations? For instance, if we apply an operation on suffix i and another on suffix j, they both affect multiple positions, but the net op array counts each operation separately. The total number of operations is sum over suffixes of the absolute number of times we apply that suffix (since each operation on a suffix is a unit step). So total ops = sum_i |op_i|, where op_i is net change from suffix i. But could the same net effect be achieved with a different representation that uses fewer total unit steps? Because op_i is not unique? Wait, is op_i uniquely determined? Let's examine: The condition f_i = sum_{j=1}^i op[j] = x - a_i. This yields unique op[1..n] given x and a. Because f is uniquely determined (differences). So any sequence of operations that results in final constant x must have cumulative net op's satisfying those equations. Because the total added to element i is f_i, and final a_i + f_i = x, so f_i = x - a_i. So indeed the net effect on each element is fixed. Then the op array is the discrete derivative of f, which is unique. So the net number of times we apply each suffix (with sign) is fixed. There is no alternative representation; any sequence of unit operations that results in the same net effect on each element must have the same net op array, because the mapping from ops to f is linear and invertible (triangular matrix). Therefore, the total number of operations is at least sum_i |op_i|. And we can achieve exactly sum_i |op_i| by applying op_i operations of appropriate sign on each suffix i. Thus the minimal operations is sum_i |op_i|.
Thus sum_i |op_i| = |x - a_1| + sum_{i=2}^n |a_{i-1} - a_i|. So minimal overall is min_x that. So indeed the minimal operations is exactly that expression, with optimal x = a_1 giving sum of absolute differences.
Thus, after change, the minimal operations is S'.
Thus answer = min_{one change} S'.
Thus our reduction formula is correct.
Now, implement.
But there might be a subtlety: The expression for interior reduction uses |a_{i-1} - a_i| + |a_i - a_{i+1}| - |a_{i-1} - a_{i+1}|. This is always >=0. But we must be careful: For interior, the new sum of differences after change is S - (original two diffs) + |a_{i-1} - v| + |v - a_{i+1}|, minimized over v. The minimum is |a_{i-1} - a_{i+1}|, so reduction = original two diffs - |a_{i-1} - a_{i+1}|. That's what we have.
But note: Could there be a scenario where we change a value such that the new first element (if p=1) leads to a different target selection that reduces the sum further? Let's think: If we change a_1 to v, then the array becomes v, a_2, ..., a_n. The minimal ops for that array is min_x (|x - v| + sum_{i=2}^{n-1} |a_i - a_{i+1}|? Actually sum of diffs for this array is |v - a_2| + sum_{i=2}^{n-1} |a_i - a_{i+1}|. That's S - |a_1 - a_2| + |v - a_2|. And we can set x = v to make first term 0, so total ops = |v - a_2| + (S - |a_1 - a_2|). That's exactly S - |a_1 - a_2| + |v - a_2|. The optimal v to minimize that is v = a_2, giving total = S - |a_1 - a_2|. So reduction = |a_1 - a_2|, as per our endpoint case. So consistent.
Thus our method covers endpoints as well.
Now, implementation is straightforward.
But hold on: In the problem statement, they mention "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." So we can also not change. That's covered because we take max_reduction; if no positive reduction, answer = S.
Now, is there any scenario where making a change could increase the sum of differences? No, we can always set v such that it doesn't increase, e.g., keep same value. So we can always achieve at most S.
Now, test a tricky case: n=3, a = [0, 10, 0]. S = 10+10=20. Reduction interior (i=2) = |0-10|+|10-0| - |0-0| = 10+10-0=20? Actually |a1-a3| = |0-0|=0, so reduction=20. So max reduction = 20, answer =0. Indeed we can change a2 to 0, making array [0,0,0], sum diff=0. Good.
Now, consider a = [0, 5, 10]. S =5+5=10. Interior i=2: |0-5|+|5-10| - |0-10| =5+5-10=0. Endpoint p=1 reduction=5, p=3 reduction=5. max reduction=5, answer=5. Could we do better? Change a2 to something? Let's try change a2 to 0: new array [0,0,10], diffs: |0-0|+|0-10| =10, ops =10. Change a2 to 10: [0,10,10], diffs:10, ops=10. Change a2 to 5: original 10. So best is 5 by changing endpoint to match neighbor. Indeed, we can change a1 to 5 => [5,5,10] diffs:0+5=5, ops=5. Or change a3 to5 => [0,5,5] diffs:5+0=5. So answer 5. Good.
Now, a = [0, -5, 10]. S =5+15=20. interior i=2: |0-(-5)|+|(-5)-10| - |0-10| =5+15-10=10. endpoints: p1 reduction=5, p3 reduction=15. max reduction=15? Actually 15 > 10. So answer =20-15=5. That would be achieved by changing a3 to -5? Actually p3 reduction = |a2 - a3| = | -5-10| =15. If we change a3 to -5, array becomes [0,-5,-5], diffs:5+0=5. So yes. Could we do better by changing interior? 20-10=10. So indeed best is 5.
Now, check if interior reduction can be larger than sum of both incident differences? No, it's at most sum of both, when |L-R|=0, reduction = sum. That occurs when L = R. So interior can achieve full reduction of both edges if neighbors are equal. For example, a = [1,5,1] gave reduction = |1-5|+|5-1| - |1-1| = 4+4-0=8. S =8, answer 0. That matches changing middle to 1 => all ones.
Thus logic seems robust.
Now, before coding, ensure we consider the possibility that after change, the sum of differences could be negative? No, absolute values.
Now, we should test on some random arrays with brute force for small n to verify. Let's do mental small n=3 exhaustive? But trust.
Now, what about scenario where the array is long, and changing one element can reduce more than the sum of its two incident differences? Not possible because reduction is bounded by that sum.
Now, consider possibility that by changing one element, we might also affect the ability to set target x = a'1, but maybe we could choose x that yields lower total than sum_diffs? But we proved minimal is sum_diffs. However, let's re-evaluate that proof: It uses the condition that final values are all x, and operations are suffix increments. That yields the system. But is it possible that we could use a sequence of operations that does not correspond to a net op array that satisfies op[i] = a{i-1} - a_i? Because we assumed that after all operations, the final array is constant. That gives f_i = x - a_i. And f_i = sum_{j=1}^i op[j]. That's forced. The op array is the first differences of f, so op[1] = f_1, op[i] = f_i - f_{i-1} for i>=2. So indeed any sequence results in some op array, but the net effect must match f_i. So op array is uniquely determined by the net f_i. So no alternative.
Thus good.
Now, any subtlety about initial array being modified? The operations apply to the modified array (after our change). So we apply the same reasoning.
Thus solution is correct.
Now, we can implement.
But wait, check sample 7 large numbers: answer 2847372102. Our code should produce that.
Now, time complexity: O(n) per test case.
Now, we need to handle t up to 1000, sum n <= 2e5.
Now, edge-case: n=2, diff array of size 1, compute max_reduction as described.
Now, what about n=2 and we change the element? Already covered.
Now, what about negative numbers? absolute differences are fine.
Now, will there be any overflow when computing reduction? Using long long.
Now, one more nuance: The formula for interior reduction uses abs(a[i-1] - a[i+1]), which may be up to 1e9, fine.
Now, I'll code.
But before finalizing, double-check with a scenario where the optimal change is not at an interior index because maybe the reduction at interior is less than at endpoints. Already we take max.
Now, what about the scenario where we don't change any element but maybe we can still achieve better by using a different target? The minimal is already S. So we are fine.
Thus answer is S - D.
Now, write code accordingly.
But we need to be careful: For interior reduction, compute red = diff[i-1] + diff[i] - abs(a[i-1] - a[i+1]). However, we must ensure i is in 1..n-2 (0-indexed). For i=0 and i=n-1, use endpoint reduction. So we can just compute directly.
Implementation steps:
For each test case:
- read n
- read vector a(n)
- if n==2: S = abs(a[0]-a[1]) D = S (since both endpoints give that reduction) ans = 0 print ans continue (or use general formula)
But general formula works for n=2.
Better to implement generic:
vector diff(n-1); long long S = 0; for i in 0..n-2: diff[i] = abs(a[i] - a[i+1]); S += diff[i]; long long best = 0; for i in 0..n-1: long long red; if (i == 0) red = diff[0]; else if (i == n-1) red = diff[n-2]; else red = diff[i-1] + diff[i] - abs(a[i-1] - a[i+1]); if (red > best) best = red; long long ans = S - best; print ans
Now, test with n=2: diff[0] exists, i=0: red = diff[0]; i=1: red = diff[0]; best = diff[0]; ans = diff[0] - diff[0] = 0. Good.
Now, with n=3: diff[0], diff[1]. i=0: red = diff[0]; i=1: red = diff[0]+diff[1] - abs(a[0]-a[2]); i=2: red = diff[1]; best = max of these; ans = S - best.
Now, test sample 3: a=[99,96,97,95] n=4. Compute diff: [3,1,2] S=6. i=0: red=3. i=1: red = diff0+diff1 - abs(a0-a2) = 3+1 - abs(99-97)=4-2=2. i=2: red = diff1+diff2 - abs(a1-a3)=1+2 - abs(96-95)=3-1=2. i=3: red = diff2=2. best=3, ans=3.
Matches.
Now, sample 5: a=[1,4,3,2,4,1] n=6 diff: [3,1,1,2,3] sum=10. i=0: red=3. i=1: red=3+1 - abs(1-3)=4-2=2. i=2: red=1+1 - abs(4-2)=2-2=0. i=3: red=1+2 - abs(3-4)=3-1=2. i=4: red=2+3 - abs(2-1)=5-1=4. i=5: red=3. best=4 ans=6.
Matches.
Now, sample 6: a=[5,0,0,0,5] diff: [5,0,0,5] sum=10. i0:5, i1:5+0 - abs(5-0)=5-5=0, i2:0+0 - abs(0-0)=0, i3:0+5 - abs(0-5)=5-5=0, i4:5 => best=5 ans=5.
Matches.
Now, sample 2: a=[-1,0,2] diff: [1,2] sum=3. i0:1, i1:1+2 - abs(-1-2)=3-3=0, i2:2 => best=2 ans=1.
Matches.
All good.
Now, sample 7: We'll test later.
Thus solution passes examples.
Now, let's also consider potential corner cases:
-
n=2, a=[-1000000000, 1000000000]. diff=2000000000, best=2000000000, ans=0. Good.
-
n=3, a=[0, 0, 0] diff=[0,0] sum=0, reductions: i0:0, i1:0+0 -0=0, i2:0 => best=0 ans=0.
-
n=3, a=[1, 1000000000, 1] diff=[999999999, 999999999] sum=1999999998, i1 reduction = 999999999+999999999 - |1-1|=1999999998, best=1999999998, ans=0. Works.
Now, think about if we need to consider long long for abs. In C++, abs for long long is llabs or std::abs with long long works? In C++11, std::abs works for long long (overloaded). But to be safe, use llabs or cast to long long. We'll use abs from ? Better to use std::abs with ? Actually, in C++, for integer types, there is overload in for int, long, long long. In competitive programming, we often just use abs on long long and it's fine (with GCC). So okay.
Now, time complexity O(total n). Memory O(n) to store a and diff. Could reduce memory by computing on the fly, but not needed.
Now, maybe there is a more nuanced trick: Could the reduction be more than what we computed if we consider also the effect on the "first term" if we change a1? But we already accounted: changing a1, the new sum diffs is S - |a1-a2| + |v-a2|, minimized when v=a2, giving reduction = |a1-a2|. So that's already included.
Now, consider changing a_i where i is interior, but maybe we could also change target x to something else and reduce further? But we already accounted that after change, the minimal ops = sum diffs. However, is there possibility that by changing a_i to v, we might make the new a'1 different, and then we could choose x not equal to a'1 to get a total less than sum diffs? Let's test: Suppose we change some interior element; a_1 remains same. Then sum diffs after change is S' = S - (|a{i-1}-a_i|+|a_i-a{i+1}|) + (|a_{i-1}-v|+|v-a_{i+1}|). The minimal total ops is min_x (|x - a_1| + S')? Wait, the formula total ops = |x - a_1| + S'? Actually, careful: In general, for array a' after change, the total ops for target x is |x - a'1| + sum{j=2}^{n} |a'_{j-1} - a'j|. That sum{j=2}^{n} |...| is exactly S'? Because S' is sum of all consecutive diffs, which includes |a'_1 - a'_2| and others. Yes, S' includes all diffs. So total ops for target x = |x - a'_1| + S'. To minimize, we set x = a'_1, giving total = S'. So no further reduction.
But what if we change a_1? Then a'_1 changes to v, and S' is sum of diffs of the new array. Then total ops min = min_x (|x - v| + S') = S' (by x=v). So again S'. So the minimal ops is always S' after change. So indeed we just need to minimize S'.
Thus our approach is correct.
Now, final step: implement and submit.
But before coding, think about potential integer overflow in computing abs of differences: a_i can be as low as -5e8, difference up to 1e9, within 32-bit signed? Actually, 1e9 fits in 32-bit signed (max 2.147e9). But sum of many could exceed, so use long long. So we cast to long long.
Now, ensure to use long long for all.
Now, additional consideration: Could the answer be negative? No, S' is non-negative. So output non-negative.
Now, also note that problem's sample 7 answer is 2847372102, which is > 2^31, so must use long long.
Now, code in C++.
Pseudo:
#include <bits/stdc++.h> using namespace std; typedef long long ll;
int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector a(n); for (int i=0; i<n; i++) cin >> a[i]; vector diff(n-1); ll S = 0; for (int i=0; i<n-1; i++) { diff[i] = abs(a[i] - a[i+1]); S += diff[i]; } ll best = 0; for (int i=0; i<n; i++) { ll red; if (n == 1) { // not possible because n>=2 // skip } if (i == 0) red = diff[0]; else if (i == n-1) red = diff[n-2]; else red = diff[i-1] + diff[i] - abs(a[i-1] - a[i+1]); if (red > best) best = red; } ll ans = S - best; cout << ans << "\n"; } return 0; }
Now, we need to ensure when n=2, diff[0] exists, i=0 uses diff[0], i=1 uses diff[0], and interior condition never reached. So ok.
Now, test with provided samples.
But before final, re-check sample 7 manually? Let's compute quickly with code mental? Not needed.
Now, think if there is any scenario where we could achieve even more reduction by changing an element to a value that also influences the first term beyond what we computed? For instance, if we change a_1, the reduction is exactly |a1-a2|. Could we also adjust the sum of other differences? No, only incident edges.
Now, perhaps there is an alternative approach: Maybe we could change an element to a value that makes the array monotonic or something, but our reduction formula captures the best possible for each position.
Now, a more subtle point: The problem allows changing one element to any integer. However, we have considered only changing to a value that minimizes the sum of the two incident differences. For interior, that's any value between neighbors. But does that choice affect the ability to set target x = a'_1? If we change an interior element, a_1 remains same, so target will be a_1. That's fine. If we change a_1 to v, we said we can set v = a_2 to get reduction, and then target = v = a_2 yields ops = |v - a_2|? Wait, if we change a_1 to a_2, then array becomes [a_2, a_2, a_3,...]. Then sum diffs = |a_2 - a_3| + ... (starting from diff between new a1 and a2 = 0). And we set target = a_2 (since a'_1 = a_2), then total ops = sum diffs. That's exactly S - |a1-a2|. So reduction is |a1-a2|. So yes.
If we change a_n to a_{n-1}, similar.
Thus all good.
Now, I think solution is correct.
But wait: There is an underlying assumption that the array index start at 1 and suffix includes a_n. Our derivation used that. Good.
Now, what about the possibility that after change, we could use a different target x that yields even smaller total than sum diffs? Let's try to construct a counterexample. Suppose we have array after change: a' = [2, 0, 2]. Then S' = |2-0|+|0-2| = 2+2=4. Our formula says minimal ops = 4 (target = 2 gives ops: |2-2|+4? Actually total ops formula: |x-2|+4. Minimizing over x gives x=2 => 4. Could we do better? Try sequence: first, we want all equal maybe to 1? Let's try manually: a' = [2,0,2]. Goal: all equal to 1. Steps: We need to go from [2,0,2] to [1,1,1]. Use suffix operations: We can think of net ops: To get x=1, we need f = x - a' => f = [-1,1,-1]? Actually f_i = x - a_i => f1 = -1, f2=1, f3=-1. But f must be prefix sums of ops: f1 = op1, f2 = op1+op2, f3 = op1+op2+op3. Solve: op1 = -1, op2 = f2 - f1 = 1 - (-1) = 2, op3 = f3 - f2 = -1 - 1 = -2. So ops count = |op1|+|op2|+|op3| = 1+2+2=5. That's more than 4. Target=0: op1 = -2, op2 = (0-2?) Let's compute f: [ -2,0,-2]? Actually a' = [2,0,2], x=0 => f = [-2,0,-2], then op1=-2, op2=2, op3=-2, sum=2+2+2=6. So 4 is indeed minimal. So sum diffs is minimal.
Now, try array [0,2,0] after change? S'=2+2=4. target=0 gives ops = |0-0|+4=4, target=2 gives |2-0|+4=6. So 4 is min. So seems consistent.
Thus answer stands.
Now, confirm with more random: a' = [1,3,4]. S' = 2+1=3. Target=1 => ops=3, target=3 => |2|+3=5, target=4 => |3|+3=6. So min=3.
Thus all good.
Now, finalize.
But hold on: There's a nuance: In our derivation of total ops, we assumed that we can set op[i] = a_{i-1} - a_i for i>=2. But these could be large. However, the fact that we can perform op[i] operations on suffix i indeed yields the result. But is there any constraint that operations must be performed one after another and the intermediate values might cause something that prevents achieving exactly that? No, because operations are linear and commutative; order doesn't matter for final result. So we can apply all operations in any order, and the net effect is additive. So we can achieve.
Now, the only subtlety: The operations are "increase all elements of a suffix by 1" or "decrease... by 1". So we can apply positive or negative increments. So net op[i] can be positive or negative. Representing op[i] as a signed integer, we can achieve that by applying |op[i]| operations: if op[i] > 0, we apply increase operations; if op[i] < 0, we apply decrease operations. So that's fine.
Thus solution is correct.
Now, code.
Potential improvements: We could avoid storing diff array by computing on the fly, but it's fine.
Now, test with sample input to ensure output matches.
We'll test sample manually:
Test1: 2,1 1 -> diff[0]=0, S=0, best = max(0,0)=0, ans=0.
Test2: 3, -1 0 2 -> diff: [1,2] S=3. i0:1; i1:1+2 - abs(-1-2)=3-3=0; i2:2. best=2, ans=1.
Test3: 4 99 96 97 95 -> diff[3,1,2] S=6. i0:3; i1:3+1 -|99-97|=4-2=2; i2:1+2 -|96-95|=3-1=2; i3:2. best=3, ans=3.
Test4: 4 -3 -5 -2 1 -> diff[2,3,3] S=8. i0:2; i1:2+3 -|-3 - (-2)|=5-1=4; i2:3+3 -|-5-1|=6-6=0; i3:3. best=4, ans=4.
Test5: 6 1 4 3 2 4 1 -> diff[3,1,1,2,3] S=10. i0:3; i1:3+1 -|1-3|=4-2=2; i2:1+1 -|4-2|=2-2=0; i3:1+2 -|3-4|=3-1=2; i4:2+3 -|2-1|=5-1=4; i5:3. best=4, ans=6.
Test6: 5 5 0 0 0 5 -> diff[5,0,0,5] S=10. i0:5; i1:5+0 -|5-0|=5-5=0; i2:0+0 -|0-0|=0; i3:0+5 -|0-5|=5-5=0; i4:5. best=5, ans=5.
Test7: We'll trust.
Thus matches.
Now, consider n=2 edge: 2 5 100 -> diff[95] S=95, best=95, ans=0.
Now, check performance: For each test case, O(n) time, sum n <= 2e5, fine.
Now, are there any potential overflow in computing diff[i-1] + diff[i]? diff values are up to 1e9, sum up to 2e9, fits in 64-bit.
Now, some languages: C++ with long long.
Now, I'll produce final answer.
But before finalizing, let's think about the possibility of multiple test cases: sum n <= 2e5, but t could be up to 1000, so many small test cases. Our code handles.
Now, potential pitfalls: When n=1? Not possible.
Now, we should also consider the scenario where we might change an element to a value that yields a sum of differences less than S - max_reduction? Could there be a scenario where the reduction from one change affects more than two differences because the change of one element also changes the optimal target selection? But target selection is independent; we already accounted that minimal ops after change is sum diffs. But what if after change, we could choose a target that is not equal to a'_1, and by doing so we might have a total ops that is less than sum diffs? But earlier we argued min_x (|x-a'_1|+S') = S' because we can set x=a'_1. But wait: If we set x=a'_1, then the total ops = S'. So S' is an achievable value. Could there be a value less than S'? That would require |x - a'_1| + S' < S' => |x - a'_1| < 0, impossible. So S' is a lower bound and achievable. So minimal is S'.
Thus no.
Thus answer is S - D.
Now, D = max over i of reduction_i.
But note: Is there any scenario where by changing one element, we could also reduce the sum of differences by more than the sum of its two incident edges? Could there be an indirect effect on other differences? Only the two edges directly involving the changed element are altered. So maximum reduction is bounded by the sum of those two edges minus the minimal possible new sum (which is |L-R|). So that's our reduction_i.
Thus solution is solid.
Now, I'll craft the final explanation for solution.
But wait, the problem's note says "minimum number of operations Gildong will perform." After we change one element, Gildong will perform operations. We're counting operations he performs. So we output that number.
Thus code.
Now, check sample 7 using code? We'll trust.
Now, potential bug: For n=2, we have diff[0] defined; interior case not used. That's fine.
Now, handle reading input.
Now, implement.
Now, about the code: We'll use fast I/O.
Now, answer.
But I've thought: Another approach: Because D = max( max(diff[0], diff[n-2]), max_{i=1..n-2} (diff[i-1] + diff[i] - abs(a[i-1] - a[i+1]) ) ).
We could compute in one loop.
Now, also consider that diff array might be empty for n=1? Not.
Now, final code.
Let's produce final answer. ```cpp
#include <bits/stdc++.h> using namespace std;
typedef long long ll;
int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
int t; cin >> t; while (t--) { int n; cin >> n; vector<ll> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; vector<ll> diff(n - 1); ll S = 0; for (int i = 0; i < n - 1; ++i) { diff[i] = abs(a[i] - a[i + 1]); S += diff[i]; } ll best = 0; for (int i = 0; i < n; ++i) { ll reduction; if (i == 0) { reduction = diff[0]; } else if (i == n - 1) { reduction = diff[n - 2]; } else { reduction = diff[i - 1] + diff[i] - abs(a[i - 1] - a[i + 1]); } if (reduction > best) best = reduction; } ll ans = S - best; cout << ans << '\n'; } return 0;}