Дан массив целых положительных чисел \(a_1, a_2, \ldots, a_n\).
Вы можете раскрасить некоторые элементы массива в красный цвет, но при этом в нем не должно оказаться двух соседних красных элементов (т.е. для \(1 \leq i \leq n-1\) хотя бы один из \(a_i\) и \(a_{i+1}\) должен не быть красным).
Ваш счет — это максимальное значение красного элемента плюс количество красных элементов. Найдите максимальный счет, который вы можете получить.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимально возможный счет, который можно получить, раскрасив некоторые элементы в красный цвет в соответствии с условием.
Примечание
В первом наборе входных данных вы можете раскрасить массив следующим образом: \([\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\). Это максимальный счет, который вы можете получить.