Задачі
Пограбування будинків
Пограбування будинків
Ви --- професіонал своєї справи і плануєте пограбувати ряд будинків уздовж вулиці. У кожному будинку захована певна сума грошей. Єдине, що заважає Вам грабувати --- так це те, що сусідні будинки пов'язані системою безпеки: буде переданий сигнал в поліцію, якщо два сусідні будинки будуть пограбовані в один і той же вечір.
Знаючи кількість грошей в кожному будинку, визначте максимальну суму, яку Ви зможете пограбувати сьогодні ввечері без попередження поліції.
\InputFile
Перший рядок містить кількість будинків $n~(1 \le n \le 10^6)$. Другий рядок містить $n$ цілих невід'ємних чисел $a_1, a_2, ..., a_n$, де $a_i$ --- кількість грошей, яке може бути винесено з $i$ - го будинку.
\OutputFile
Виведіть максимальну суму, яку Ви зможете пограбувати сьогодні ввечері без надходження сигналу в поліцію.
\includegraphics{https://static.e-olymp.com/content/76/76e782c6f5adf67a890b17ecc7c6ddba0cc591bc.gif}
Вхідні дані #1
5 6 1 2 10 4
Вихідні дані #1
16