Codeforces Round 975 (Div. 1) |
---|
Закончено |
Дан массив целых положительных чисел $$$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$$$.
Для каждого набора входных данных выведите одно целое число: максимально возможный счет, который можно получить, раскрасив некоторые элементы в красный цвет в соответствии с условием.
435 4 534 5 4103 3 3 3 4 1 2 3 5 41017 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$$$. Это максимальный счет, который вы можете получить.
Название |
---|