Maximizing Gold Coins in the Magical Forest

You are wandering in a mysterious forest filled with enchanted trees. Each tree bears a certain number of gold coins. However, a powerful curse prevents you from collecting coins from two adjacent trees. In other words, if you take coins from the i^th tree, you must skip the (i+1)^th tree.

Your task is to maximize the total number of gold coins you can collect following this rule.

Mathematically, given a sequence of coins \(a_1, a_2, \dots, a_N\) on N trees, you need to choose a subset of trees such that no two consecutive trees are selected, and the sum of the coins is maximized.

Example: For \(N = 5\) and coins \([1, 2, 9, 4, 5]\), the maximum coins you can collect is \(15\) (by picking trees with 1, 9, and 5 coins, respectively).

inputFormat

The input is given via standard input (stdin) and consists of two lines:

• The first line contains a single integer N — the number of trees in the forest.
• The second line contains N non-negative integers separated by spaces, where the i^th integer represents the number of gold coins on the i^th tree.

outputFormat

Output a single integer to standard output (stdout) — the maximum number of gold coins that can be collected without picking coins from two consecutive trees.

5
1 2 9 4 5

15