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

A. Максимум + количество
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
EnV - Dynasty
⠀

Дан массив целых положительных чисел $$$a_1, a_2, \ldots, a_n$$$.

Вы можете раскрасить некоторые элементы массива в красный цвет, но при этом в нем не должно оказаться двух соседних красных элементов (т.е. для $$$1 \leq i \leq n-1$$$ хотя бы один из $$$a_i$$$ и $$$a_{i+1}$$$ должен не быть красным).

Ваш счет — это максимальное значение красного элемента плюс количество красных элементов. Найдите максимальный счет, который вы можете получить.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 100$$$) — длина массива.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 1000$$$) — заданный массив.

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

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

Пример
Входные данные
4
3
5 4 5
3
4 5 4
10
3 3 3 3 4 1 2 3 4 5
9
17 89 92 42 29 92 14 70 45
Выходные данные
7
6
10
97
Примечание

В первом наборе входных данных вы можете раскрасить массив следующим образом: $$$[\color{red}{5}, 4, \color{red}{5}]$$$. Ваш счет составит $$$\max([5, 5]) + \text{size}([5, 5]) = 5+2 = 7$$$. Это максимальный счет, который вы можете получить.

Во втором наборе входных данных вы можете раскрасить массив следующим образом: $$$[\color{red}{4}, 5, \color{red}{4}]$$$. Ваш счет составит $$$\max([4, 4]) + \text{size}([4, 4]) = 4+2 = 6$$$. Это максимальный счет, который вы можете получить.

В третьем наборе входных данных вы можете раскрасить массив следующим образом: $$$[\color{red}{3}, 3, \color{red}{3}, 3, \color{red}{4}, 1, 2, \color{red}{3}, 4, \color{red}{5}]$$$. Ваш счет составит $$$\max([3, 3, 4, 3, 5]) + \text{size}([3, 3, 4, 3, 5]) = 5+5 = 10$$$. Это максимальный счет, который вы можете получить.