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

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

Вхідні дані

Перший рядок містить кількість будинків \(n\) (\(1≤n≤10^6\)).

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

Вихідні дані

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

Вхідні дані #1

5
6 1 2 10 4

Відповідь #1

16