Ограбление домов
Ограбление домов
Вы — профессионал своего дела и планируете ограбить ряд домов вдоль улицы. В каждом доме спрятана определенная сумма денег. Единственное, что мешает Вам грабить — так это то, что соседние дома связаны системой безопасности: будет передан сигнал в полицию, если два соседние дома будут ограблены в один и тот же вечер.
Зная количество денег в каждом доме, определите максимальную сумму, которую Вы сможете ограбить сегодня вечером без уведомления полиции.
Входные данные
Первая строка содержит количество домов n~(1 \le n \le 10^6). Вторая строка содержит n целых неотрицательных чисел a_1, a_2, ..., a_n, где a_i — количество денег, которое может быть вынесено из i-го дома.
Выходные данные
Выведите максимальную сумму, которую Вы сможете ограбить сегодня вечером без поступления сигнала в полицию.
Пример
5 6 1 2 10 4
16