Non-Adjacent Maximum Sum

Medium#dynamic-programming· solved by 0 · time limit 2.0 s

Pick some elements so that no two picked elements are next to each other, maximising their sum. All values are non-negative.

Input

$n$ , then $n$ integers.

The maximum sum.

$1 \le n \le 10^5$ , $0 \le a_i \le 10^4$

Input

4
1 2 3 1

Output

Input

5
2 7 9 3 1

Output