Вы — профессионал своего дела и планируете ограбить ряд домов вдоль улицы. В каждом доме спрятана определенная сумма денег. Единственное, что мешает Вам грабить — так это то, что соседние дома связаны системой безопасности: будет передан сигнал в полицию, если два соседние дома будут ограблены в один и тот же вечер.
Зная количество денег в каждом доме, определите максимальную сумму, которую Вы сможете ограбить сегодня вечером без уведомления полиции.
Первая строка содержит количество домов n (1≤n≤106). Вторая строка содержит n целых неотрицательных чисел a1,a2,...,an, где ai — количество денег, которое может быть вынесено из i-го дома.
Выведите максимальную сумму, которую Вы сможете ограбить сегодня вечером без поступления сигнала в полицию.