C. Buffet Line
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are standing in line for the buffet at a recruiting event. The buffet consists of a sequence of food items, where each item has a different desirability. You can choose to add each item to your plate, or to skip it.

You want to maximize the total desirability of the food on your plate; however, to avoid being selfish, you don't want to take two consecutive items from the buffet. In other words, if you choose to add item $$$i$$$ to your plate, then you must choose to skip item $$$i+1$$$.

Given this constraint, what is the maximum desirability of the food on your plate, if you choose to add items optimally?

Input

The first line of input contains a single integer $$$n$$$ $$$(1 \leq n \leq 10\,000)$$$, the number of food items in the buffet.

The next line consists of $$$n$$$ space-separated integers $$$d_i$$$ $$$(0 \leq d_i \leq 1\,000)$$$, the desirability of the $$$i$$$th food item in the buffet.

Output

Print the maximum possible total desirability of the food on your plate, if you choose to add items optimally without taking two consecutive items from the buffet.

Examples
Input
5
3 8 10 2 0
Output
13
Input
7
0 9 10 2 0 0 0
Output
11
Input
1
42
Output
42