Problem 3# - Wire Scoring

general
1

Hello everyone!!! What answer did you get for the NCS circle lounge problem? Reply what answer you got!!! This one is very tough, even though its easy to understand, its hard to replicate into code. Only competitive programmers can solve this. Others can try to get it. Reply what code you got and the language. If your answer is wrong and fails a sample, I’ll give that sample which falls that code, because even I can’t solve it, lol. I somehow got an idea to make it.

Wise Scoring

Chef wants to test how wise his choices are.

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. Update the remaining elements:
  • If the removed element had both a left and a right neighbour, each of those neighbours decreases by 1.
  • If the removed element was the leftmost element, the first two remaining elements each decrease by 1 (if they exist).
  • If the removed element was the rightmost element, the last two remaining elements each decrease by 1 (if they exist).

Chef may choose the removal order however he likes.

Determine the maximum possible score Chef can obtain.

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
0 ≤ Ai ≤ 10^9

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

Sample Input

2
3
5 4 4
4
3 8 2 7

Sample Output

9
15

Explanation

Test Case 1

One optimal sequence is:

Initial array:

5 4 4

Choose the leftmost element (5).

Score:

5

Remaining array:

4 4

Since the removed element was the leftmost, the next two remaining elements decrease by 1.

3 3

Choose 3.

Score:

8

Remaining:

2

Choose 2.

Final score:

10