Nasser's Array Equalizer#12481
Nasser gives you an array of length .
In one operation, you can choose any two indices and (1 \le l \le r \le n) and set all elements a[l], a[l+1], \ldots, a[r] to any integer between and 10^9 (inclusive). The cost of this operation is the maximum element in that subarray before the change.
You can perform this operation any number of times (possibly zero). The total cost is the sum of the costs of all operations performed.
Your task is to make all elements of the array equal to each other while minimizing the total cost.
Each test contains multiple test cases. The first line contains a single integer (1 \le t \le 10^4) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer (1 \le n \le 2 \cdot 10^5) — the length of the array.
The second line of each test case contains integers a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9) — the elements of the array.
It is guaranteed that the sum of over all test cases does not exceed 2 \cdot 10^5.
For each test case, print a single integer — the minimum total cost required to make all array elements equal.
Example 1
Subtask ( points) : (a_i \le 2)
Subtask ( points) : (1 \le \sum n \le 2000)
Subtask ( points) : No additional constraints.