D. Max Plus Min Plus Size
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
EnV - The Dusty Dragon Tavern
⠀

You are given an array $$$a_1, a_2, \ldots, a_n$$$ of positive integers.

You can color some elements of the array red, but there cannot be two adjacent red elements (i.e., for $$$1 \leq i \leq n-1$$$, at least one of $$$a_i$$$ and $$$a_{i+1}$$$ must not be red).

Your score is the maximum value of a red element, plus the minimum value of a red element, plus the number of red elements. Find the maximum score you can get.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the given array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer: the maximum possible score you can get after coloring some elements red according to the statement.

Example
Input
4
3
5 4 5
3
4 5 4
10
3 3 3 3 4 1 2 3 5 4
10
17 89 92 42 29 41 92 14 70 45
Output
12
11
12
186
Note

In the first test case, you can color the array as follows: $$$[\color{red}{5}, 4, \color{red}{5}]$$$. Your score is $$$\max([5, 5]) + \min([5, 5]) + \text{size}([5, 5]) = 5+5+2 = 12$$$. This is the maximum score you can get.

In the second test case, you can color the array as follows: $$$[4, \color{red}{5}, 4]$$$. Your score is $$$\max([5]) + \min([5]) + \text{size}([5]) = 5+5+1 = 11$$$. This is the maximum score you can get.

In the third test case, you can color the array as follows: $$$[\color{red}{3}, 3, \color{red}{3}, 3, \color{red}{4}, 1, 2, \color{red}{3}, 5, \color{red}{4}]$$$. Your score is $$$\max([3, 3, 4, 3, 4]) + \min([3, 3, 4, 3, 4]) + \text{size}([3, 3, 4, 3, 4]) = 4+3+5 = 12$$$. This is the maximum score you can get.