Maximum Gold Coins

You are given n treasure chests arranged in a line. Each chest contains a non-negative integer number of gold coins. You need to collect as many coins as possible but with the restriction that you cannot pick two adjacent chests. In other words, if you pick chest i (containing c_i coins), you cannot pick chest i-1 or chest i+1.

The problem can be formulated as follows. Let \(dp[i]\) be the maximum coins you can collect from the first \(i+1\) chests. The recurrence is given by:

[ \begin{aligned} dp[0] &= c_0,\ dp[1] &= \max(c_0, c_1),\ dp[i] &= \max(dp[i-1], dp[i-2] + c_i) \quad \text{for } i \ge 2. \end{aligned} ]

Your task is to implement a program that reads the number of chests and the coins in each chest from the standard input, computes the maximum amount of coins that can be collected without opening two consecutive chests, and prints the result to the standard output.

inputFormat

The input is given from standard input and consists of:

1. An integer n indicating the number of treasure chests. (0 \(\le\) n \(\le\) 10⁵)
2. If n > 0, the next line contains n space-separated non-negative integers where the i-th integer represents the number of coins in the i-th chest.

outputFormat

Output a single integer representing the maximum number of gold coins that can be collected without picking two adjacent chests.

0

0