New Labyrinth of Amber
Once, Corwin, the prince of Amber, urgently needed to reach the farthest shadow he knew for an important matter. As everyone knows, the fastest way for the princes of Amber to travel is through the Amber Labyrinth. However, Corwin's matter was so pressing that he didn't want to waste time descending into the dungeon where the Amber Labyrinth is located. Instead, he decided to use the New Labyrinth, drawn by Dworkin. But this Labyrinth is not as straightforward as it seems...
The New Labyrinth consists of a sequence of cells, numbered from 1 to N. From cell i, you can move to cell i+2 (if i+2 ≤ N) or to cell i+3 (if i+3 ≤ N). Each cell contains a certain number of gold coins, k_i. To navigate the labyrinth, you start from outside (from cell zero) and move according to the rules above, collecting all the coins in the cells where you stop. The ultimate goal is to reach cell N. Further travel (to any place in the Universe) is only possible if, upon reaching cell N, you have collected the maximum number of coins. Write a program to help Corwin determine the maximum number of coins that can be collected while traversing the New Labyrinth of Amber.
Input
The first line of the input file contains a natural number N (2 ≤ N ≤ 100000). The second line contains N integers, separated by spaces, k_i – the number of coins in cell i (0 ≤ k_i ≤ 1000).
Output
Output a single integer – the maximum number of coins that can be collected while passing through the labyrinth.