Maximum Chocolates from Jars (LeetCode 198)

Each jar holds a non-negative integer number of chocolates. Take some jars from a row of jars, without taking two adjacent jars, and find the maximum number of chocolates. You may take no jars at all.

输入格式

First n is given, then n non-negative counts. The original bound 1≤n≤1000 is kept. The original upper bound on values is missing; this site adds 0..10^9 and does not adopt the unsourced cap of 10000 from the catalog.

输出格式

Output a single integer, the answer.

样例 1

输入：

4
5 1 1 5

输出：

10

样例 2

输入：

1
1

输出：

1

样例 3

输入：

3
0 0 0

输出：

0

样例说明

The outputs of the three public examples are, in order: 10; 1; 0. Verified by independent enumeration or direct simulation.