Не брать соседей

Дан ряд из $n$ чисел. Выберите из них несколько так, чтобы никакие два выбранных не стояли рядом, и сумма была наибольшей.

Можно не выбирать ничего — тогда сумма равна нулю.

В первой строке число $n$ от $1$ до $10^6$. Во второй — $n$ чисел от $-10^9$ до $10^9$.

Одно число.

Для каждой позиции полезно знать два числа: лучшую сумму, если эту позицию взяли, и лучшую, если не взяли. Каждое выражается через два предыдущих, и весь массив хранить не нужно.