CF2018D.Max Plus Min Plus Size

EnV - 尘龙酒馆

---

给定一个由正整数组成的数组 $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$ 。这是你能得到的最高分。