B. Suffix Operations

B. Suffix Operations

time limit per test

1 second

memory limit per test

512 megabytes

input

standard input

output

standard output

Gildong has an interesting machine that has an array aa with nn integers. The machine supports two kinds of operations:

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

A suffix is a subsegment (contiguous elements) of the array that contains anan. In other words, for all ii where aiai is included in the subsegment, all ajaj's where i

Gildong wants to make all elements of aa 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 tt (1≤t≤10001≤t≤1000).

Each test case contains two lines. The first line of each test case consists of an integer nn (2≤n≤2⋅1052≤n≤2⋅105) — the number of elements of the array aa.

The second line of each test case contains nn integers. The ii-th integer is aiai (−5⋅108≤ai≤5⋅108−5⋅108≤ai≤5⋅108).

It is guaranteed that the sum of nn in all test cases does not exceed 2⋅1052⋅105.

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

Copy

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

计算机科学工程：在米兰理工大学攻读工程学，计算机科学工程学士学位和硕士学位，所有课程及其材料的集合

zip 0星 超过10%的资源 1851.97MB

下载

Copy

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 a3a3 to be 00, so that the array becomes [−1,0,0][−1,0,0]. Now Gildong can use the 22-nd operation once on the suffix starting at a2a2, which means a2a2 and a3a3 are decreased by 11, making all elements of the array −1−1.

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

• Use the 22-nd operation on the suffix starting at a3a3 once, making the array [96,96,96,94][96,96,96,94].
• Use the 11-st operation on the suffix starting at a4a4 22 times, making the array [96,96,96,96][96,96,96,96].

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

• Use the 22-nd operation on the suffix starting at a4a4 33 times, making the array [−3,−3,−2,−2][−3,−3,−2,−2].
• Use the 22-nd operation on the suffix starting at a3a3 once, making the array [−3,−3,−3,−3][−3,−3,−3,−3].
• =====================================================================

首先可以发现在不改变任何ai的情况下，使得全部相等的最小花费是相邻数字差值绝对值之和。

然后我们考虑枚举改变的位置

ai-1 ai  ai+1

原来ai贡献的代价是 |ai-ai-1|  + |ai+1-ai|

suffix tree—后缀树的典型应用

application/pdf 4星 超过75%的资源 622KB

下载

我们考虑给ai加上b

|ai+b-ai-1| + |ai+1 -ai-b|

令ai+b -ai-1=x

ai+1 -ai -b =y

得 |x|+|y|>=|x+y|=|ai-1-ai+1|

也就是把中间的数字变成左边的，或者变成右边的会取得缩小之后的最小值

ai-1 ai-1 ai+1

ai-1 ai+1 ai+1 

两种情况是等价的

当然还需要特判i=1,i=n的情况，直接减去各自的贡献即可

#include 
using namespace std;
typedef long long int ll;
 
ll a[200000+10];
int b[200000+10];
int main()
{
 
  int t;
 
  cin>>t;
 
  while(t--)
  {
      ll n;
 
      cin>>n;
 
      for(int i=1;i<=n;i++)
      {
          cin>>a[i];
      }
 
      ll ans=0;
      for(int i=2;i<=n;i++)
      {
          b[i]=abs(a[i]-a[i-1]);
 
          ans+=b[i];
      }
      ll mx=1e18;
      for(int i=2;i
      {
          mx=min(mx,ans-abs(a[i]-a[i-1])-abs(a[i]-a[i+1])+abs(a[i-1]-a[i+1]));
      }
      mx=min(mx,ans-abs(a[1]-a[2]));
 
      mx=min(mx,ans-abs(a[n-1]-a[n]));
 
      cout<
 
  }
 
    return 0;
}