Question
Redundant Array
Chef has an array A containing N positive integers. He can perform the following operation on the array as many times as he likes:
- Choose integers L and R such that 1 ≤ L ≤ R ≤ N;
- Choose a positive integer x;
- For every index i from L to R (inclusive of both), set Ai = x.
The cost of such an operation is (R − L + 1 )⋅x. Find the minimum cost required to make all the elements of A equal.
Input
The first line of input will contain a single integer T, denoting the number of test cases.
Each test case consists two lines of input.
The first line of each test case contains a single integer N - the size of the array.
The second line contains N space-separated integers, denoting an array A.
Constraints
1 ≤ T ≤ 2x105
1 ≤ N ≤ 2x105
1 ≤ Ai ≤ N
Sum of N over all test cases doesn't exceed 2x105
Each test case consists two lines of input.
The first line of each test case contains a single integer N - the size of the array.
The second line contains N space-separated integers, denoting an array A.
Constraints
1 ≤ T ≤ 2x105
1 ≤ N ≤ 2x105
1 ≤ Ai ≤ N
Sum of N over all test cases doesn't exceed 2x105
Output
For each test case, output on a new line the minimum cost needed to make all the elements of A equal.
Example
Sample Input
2
5
2 4 3 2 2
3
3 3 3
Sample Output
4
0
Explanation
Test case 1: Apply the operation L = 2, R = 3, x = 2. This has a cost of (3 - 2 + 1).2 = 4. The array becomes [2, 2, 2, 2, 2], and all its elements are equal. It can be proved that achieving a cost strictly less than 4 isn't possible.
Test case 2: All the elements are already equal, no operations are needed.
2
5
2 4 3 2 2
3
3 3 3
Sample Output
4
0
Explanation
Test case 1: Apply the operation L = 2, R = 3, x = 2. This has a cost of (3 - 2 + 1).2 = 4. The array becomes [2, 2, 2, 2, 2], and all its elements are equal. It can be proved that achieving a cost strictly less than 4 isn't possible.
Test case 2: All the elements are already equal, no operations are needed.