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

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

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

Вхідні дані

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

Вихідні дані

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

Приклади