Tallest Chocolate Stack

Jars are arranged in a line. You may choose any number of jars, but you cannot choose two adjacent jars; you take all the chocolates in the chosen jars. Find the maximum total. Empty jars are allowed, and taking nothing is also allowed. The first and last jars are not adjacent.

输入格式

The first line contains N, and the second line contains N non-negative chocolate counts. The OCR gives 1<N≤1000, while the complete Fastprep version of the same problem explicitly gives 1≤N≤1000; this site follows the latter so that a single jar is covered. The original has no upper bound on the count in a jar; this site adds 0≤a[i]≤10^9.

输出格式

Output a single integer, the answer.

样例 1

输入：

6
5 30 99 60 5 10

输出：

114

样例 2

输入：

1
9

输出：

9

样例 3

输入：

3
9 0 9

输出：

18

样例说明

The outputs of the three public examples are, in order: 114; 9; 18. Verified by independent enumeration or direct simulation.