Well, this is an interesting question and deals with a new (for us) and interesting concept. Have a try..

Santa Claus has lined up a row of bowls, each containing some chocolates. Nikhil has been told that he can pick up as many of these bowls as he wants, provided that he never picks two consecutive bowls.

Your aim is to help Nikhil choose a set of bowls so that he maximizes the number of chocolates that he picks up.

Input format

The first line of the input contains one integer N, the number of bowls. This is followed by a line containing N integers, describing the number of chocolates in each of the N bowls.

Notes

In all cases, N ≤ 100,000.

Output format

Your output should be a single line consisting of one integer, the maximum number of chocolates that Nikhil can collect.

Sample Input

10 

30 10 8 20 11 12 25 13 20 19 

Sample Output

95

You can post your solution/logic/hints as a comment.