Задача 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