给定一个正整数数组 $$$a_1, a_2, \ldots, a_n$$$。
您可以将数组的某些元素着色为红色,但不能有两个相邻的红色元素(即,对于 $$$1 \leq i \leq n-1$$$,$$$a_i$$$ 和 $$$a_{i+1}$$$ 中至少之一不得为红色)。
您的分数是红色元素的最大值,加上红色元素的最小值,再加上红色元素的数量。找出你能得到的最高分。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 给定的数组。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数:根据语句将某些元素着色为红色后可以获得的最大可能分数。
示例
输入 #1
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
输出 #1
12 11 12 186
注意
在第一个测试用例中,您可以按如下方式为数组着色:$$$[\color{red}{5}, 4, \color{red}{5}]$$$。您的得分为 $$$\max([5, 5]) + \min([5, 5]) + \text{size}([5, 5]) = 5+5+2 = 12$$$。这是您可以获得的最高分数。
在第二个测试用例中,您可以按如下方式为数组着色:$$$[4, \color{red}{5}, 4]$$$。您的得分为 $$$\max([5]) + \min([5]) + \text{size}([5]) = 5+5+1 = 11$$$。这是您可以获得的最高分数。
在第三个测试用例中,您可以按如下方式为数组着色:$$$[\color{red}{3}, 3, \color{red}{3}, 3, \color{red}{4}, 1, 2, \color{red}{3}, 5, \color{red}{4}]$$$。您的得分为 $$$\max([3, 3, 4, 3, 4]) + \min([3, 3, 4, 3, 4]) + \text{size}([3, 3, 4, 3, 4]) = 4+3+5 = 12$$$。这是您可以获得的最高分数。