eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Пограбування будинків

Пограбування будинків

Ліміт часу 3 секунди
Ліміт використання пам'яті 128 MiB

Ви — професіонал своєї справи і плануєте пограбувати ряд будинків уздовж вулиці. У кожному будинку захована певна сума грошей. Єдине, що заважає Вам грабувати — так це те, що сусідні будинки пов'язані системою безпеки: буде переданий сигнал в поліцію, якщо два сусідні будинки будуть пограбовані в один і той же вечір.

Знаючи кількість грошей в кожному будинку, визначте максимальну суму, яку Ви зможете пограбувати сьогодні ввечері без попередження поліції.

Вхідні дані

Перший рядок містить кількість будинків n~(1 \le n \le 10^6). Другий рядок містить n цілих невід'ємних чисел a_1, a_2, ..., a_n, де a_i — кількість грошей, яке може бути винесено з i - го будинку.

Вихідні дані

Виведіть максимальну суму, яку Ви зможете пограбувати сьогодні ввечері без надходження сигналу в поліцію.

Приклад

Вхідні дані #1
5
6 1 2 10 4
Вихідні дані #1
16