CF2018D Max Plus Min Plus Size

[EnV - 尘龙酒馆](https://soundcloud.com/envyofficial/env-the-dusty-dragon-tavern) ---------------- 给定一个由正整数组成的数组 $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$ 。

对于每个测试用例，输出一个整数：根据题意将某些元素染成红色后可能得到的最大分数。 **样例解释** 在第一个测试用例中，可以对数组着色如下： $[\color{red}{5}\color{black}, 4, \color{red}{5} \color{black}]$ .您的得分是 $\max([5, 5]) + \min([5, 5]) + \text{size}([5, 5]) = 5+5+2 = 12$ 。这是你能得到的最高分。 在第二个测试案例中，您可以对数组着色如下： $[4, \color{red}{5},\color{black} 4]$ .您的得分是 $\max([5]) + \min([5]) + \text{size}([5]) = 5+5+1 = 11$ 。这是你能得到的最高分。 在第三个测试案例中，您可以对数组着色如下： $[\color{red}{3}\color{black}, 3, \color{red}{3} \color{black},3, \color{red}{4}\color{black}, 1, 2, \color{red}{3}, \color{black}5, \color{red}{4} \color{black}]$ .您的得分是 $\max([3, 3, 4, 3, 4]) + \min([3, 3, 4, 3, 4]) + \text{size}([3, 3, 4, 3, 4]) = 4+3+5 = 12$ 。这是你能得到的最高分。

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.