Problem#4 - Wise Scoring(Hard)

general
1

Hello everyone!!! How are you doing with the Easy version of Wise Scoring?? (I know it’s hard, I’m trying to find a solution.) This is the Hard version of the problem. I hope you all solve it!!! This may need keen observations, higher than the easy one. And like what is said before, give me the code and the language, if it is wrong, ill try to find a sample that fails your code.

Wise Scoring (Hard)

This is the hard version of the problem. Here, the elements of the array decrease by X - 1.

Chef is testing whether he is truly wise.

He is given an array A of N integers.

Initially, Chef’s score is 0.

While the array is not empty, Chef performs the following operation:

  1. Choose any remaining element.
  2. Add its current value to his score.
  3. Remove the chosen element from the array.
  4. Let the removed value be X.
  5. Update the remaining elements:
  • If the removed element had both a left and a right neighbour, each of those neighbours decreases by X - 1.
  • If the removed element was the leftmost element, the first two remaining elements each decrease by X - 1(if they exist).
  • If the removed element was the rightmost element, the last two remaining elements each decrease by X - 1(if they exist).

Chef may choose the order of removals in any way.

Determine the maximum possible score.

Input Format

  • The first line contains a single integer T, the number of test cases.

  • Each test case consists of two lines.

  • The first line contains a single integer N.

  • The second line contains N space-separated integers

    A1,A2,…,AN

Output Format

For each test case, print a single integer — the maximum score Chef can obtain.

Constraints

1 ≤ T ≤ 10^4
1 ≤ N ≤ 2 × 10^5
1 ≤ Ai ≤ 10^9

Sum of N over all test cases ≤ 2 × 10^5

Sample Input

3
3
100 2 100
3
5 1 100
4
3 8 2 7

Sample Output

198
102
8

Explanation

Test Case 1

Initial array:

100 2 100

Choose 2.

Score:

2

The remaining array becomes:

100 100

Since 2 was removed from the middle, both neighbours decrease by

2 − 1 = 1

Result:

99 99

Remove one 99.

Score:

101

The remaining element decreases by

99 − 1 = 98

Result:

1

Remove 1.

Final score:

102

Good luck! I hope someone makes this one.