Задача D. Подготовка к ЕГЭ ≡

Условие

Мальчик Миша готовится экзаменам. На это у него осталось N дней. В i-ый день у Миши вдохновение решить a_i задач. Но он не сверхчеловек, поэтому ему необходимо спать. В i-ый день у Миши есть выбор:

• Поспать, не решив ни одной задачки.
• Выпить чай с лимонником и не спать, решив все задачи.
• Не спать, решив все задачи.

Не спать он может только в том случае, если у него достаточно сил, то есть если в предыдущий день он поспал.

Также у него есть замечательный напиток — чай с лимонником, который даст ему сил не спать. Но при этом Миша знает, что избыток чая вреден для здоровья, поэтому он не станет его пить, если делал это в предыдущий день.

Формат входных данных

В первой строке записано целое число N.

Во второй строке находится N целых чисел a_i.

Формат выходных данных

Выведите одно целое число: максимальное количество задач, которые может решить Миша.

Ограничения

1 ≤ N ≤ 2 ⋅ 10⁵

1 ≤ a_i ≤ 10⁶

Система оценки и описание подзадач

Баллы начисляются за каждый тест независимо. Тесты поделены по подзадачам, описанным ниже.

Примеры тестов

3
1 2 3

5

5
1 1 1 1 1

4

Разбор

Решим задачу при помощи динамического программирования. Создадим 3 массива длины N, где в первом на i-ой позиции будет храниться максимальное количество задач, решенное к i-ому дню включительно, если в этот день Миша решит поспать. Во втором — если решит попить чай. А в третьем — если решит не спать.

База динамики: в первом массиве на первой позиции будет стоять 0, так как Миша будет спать и не решит задач. Во втором и третьем массивах на первой позиции будет стоять a₁.

Далее для всех i от 2 до N на i-ой позиции:

• первого массива — максимум из значений всех массивов на позиции i − 1;
• второго массива — сумма a_i и максимума из значений первого и третьего массивов на позиции i − 1;
• третьего массива — сумма значения первого массива на i − 1 позиции и a_i.

Ответом будет максимум из элементов на N-ой позиции всех трёх массивов.