Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

D. Максимум + минимум + количество
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число: максимально возможный счет, который можно получить, раскрасив некоторые элементы в красный цвет в соответствии с условием.

Пример
Входные данные
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
Примечание

В первом наборе входных данных вы можете раскрасить массив следующим образом: $$$[\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$$$. Это максимальный счет, который вы можете получить.