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.

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.

Max Plus Min Plus Size

Examples