D. 最大值 + 最小值 + 个数

时间限制：每个测试点 $2$ 秒
内存限制：$256$ MB

---

题目描述

给你一个由正整数组成的数组 $a_1, a_2, \dots, a_n$。

你可以将其中一些元素染成红色，但不能有两个相邻的红色元素（即对于 $1 \le i \le n-1$，$a_i$ 和 $a_{i+1}$ 不能同时为红色）。

你的得分定义为：

$$\text{得分} = \max(\text{红色元素}) + \min(\text{红色元素}) + \text{红色元素个数} $$

请你求出能获得的最大得分。

---

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

每个测试用例：

• 第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示数组的长度。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示数组中的元素。

保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

---

输出格式

对于每个测试用例，输出一个整数：按照题目要求染色后，能获得的最大得分。

---

示例

输入

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

输出

12
11
12
186

---

样例解释

第一个测试用例：
数组为 $[5,4,5]$，可以染成 $[5,4,5]$（红色为第 $1$ 个和第 $3$ 个元素）。
得分 = $\max(5,5) + \min(5,5) + 2 = 5 + 5 + 2 = 12$。

第二个测试用例：
数组为 $[4,5,4]$，可以只染第 $2$ 个元素 $[4,5,4]$。
得分 = $\max(5) + \min(5) + 1 = 5 + 5 + 1 = 11$。

第三个测试用例：
数组为 $[3,3,3,3,4,1,2,3,5,4]$，可以染第 $1,3,5,7,9$ 个元素：$[3,3,3,3,4,1,2,3,5,4]$。
得分 = $\max(3,3,4,3,4) + \min(3,3,4,3,4) + 5 = 4 + 3 + 5 = 12$。