Maximum Coin Collection

You are given an array of integers representing coins in your piggy bank. Your task is to select a subset of these coins such that no two chosen coins are adjacent in the original array, and the sum of the selected coins is maximized. If all coins have negative values, the answer should be 0.

This problem is a variation of the classic House Robber problem. The recurrence relation to solve the problem is given by:

Your program should read input from standard input (stdin) and print the result to standard output (stdout).

inputFormat

The input consists of two lines. The first line contains a single integer $n$, representing the number of coins. The second line contains $n$ space-separated integers that represent the values of the coins.

outputFormat

Output a single integer that represents the maximum sum of coins that can be collected without selecting any two adjacent coins.## sample

5
3 2 5 10 7

15