C. Banana Lounge
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Busy Beaver loves spending his afternoons at MIT's Banana Lounge. He decides to help out by stacking banana boxes! He needs to collect the inventory across $$$N$$$ consecutive rooms, arranged in a single row and numbered $$$1$$$ to $$$N$$$ from left to right. Due to the quirky architecture of MIT's buildings, each room $$$i$$$ has a specific ceiling clearance height, $$$h_i$$$.

Busy Beaver needs to select one room $$$k$$$ ($$$1 \le k \le N$$$) to serve as the Main Hub. Then, $$$N$$$ of his friends, one from each room, each carry a vertical stack of banana boxes from their starting room $$$i$$$ directly to the hub room $$$k$$$. Since they must walk in a straight line, the maximum number of boxes they can carry is limited by the minimum clearance on their path.

Formally, the number of banana boxes delivered by the friend starting at room $$$i$$$ to the hub room $$$k$$$ is:

  • $$$\min(h_i, h_{i+1}, \dots, h_k)$$$ if $$$i \le k$$$.
  • $$$\min(h_k, h_{k+1}, \dots, h_i)$$$ if $$$i \gt k$$$.
The total number of banana boxes gathered at the hub is the sum of the boxes delivered by all $$$N$$$ friends, which is: $$$$$$ \sum_{i = 1}^{k - 1}\min(h_i,\dots,h_k) + h_k + \sum_{i = k + 1}^N \min(h_k,\dots,h_i) $$$$$$ Fortunately, Busy Beaver has a friend in MIT Facilities. Before the friends start carrying the boxes, he can request to renovate at most one room (which cannot be the chosen hub room $$$k$$$) to change its clearance height $$$h_i$$$ to any value.

What is the maximum total number of banana boxes Busy Beaver can gather at the Main Hub after choosing the optimal hub location $$$k$$$ and performing at most one ceiling renovation?

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \leq 10^5$$$) — the number of test cases.

The first line of each test case contains a single integer $$$N$$$ ($$$2 \leq N \leq 10^6$$$).

The next line of each test case contains $$$N$$$ space-separated integers $$$h_1,h_2,\dots,h_N$$$ ($$$1 \leq h_i \leq 10^9$$$).

The sum of $$$N$$$ across all test cases does not exceed $$$10^6$$$.

Output

For each test case, output one line containing one integer: the answer for the test case.

Scoring

There are two subtasks for this problem.

  • ($$$30$$$ points): The sum of $$$N$$$ across all test cases does not exceed $$$3\cdot 10^3$$$.
  • ($$$70$$$ points): No additional constraints.
Example
Input
2
5
1 10 1 10 1
5
10 10 10 10 10
Output
32
50
Note

In the first sample case, the best option is to choose hub $$$k = 2$$$ and renovate $$$h_3$$$ to at least $$$10$$$, allowing the middle three friends to all carry $$$10$$$, for a total of $$$32$$$.

In the second sample case, no renovation can increase the number of banana boxes, so the answer is $$$50$$$.