Maximum Gold Coins

You are given a row of N treasure chests. The i-th chest contains A_i gold coins. However, there is a catch: you cannot open three consecutive chests, because doing so will trigger an alarm. In other words, if you open two consecutive chests, you must skip opening the next one.

Your task is to determine the maximum number of gold coins you can collect without triggering the alarm.

The problem can be formulated as follows:

Given an integer \(N\) and an array \(A\) of length \(N\), find the maximum sum of a subsequence of \(A\) such that you never choose coins from three consecutive chests.

Hint: A dynamic programming approach works well for this problem. One way to define the state is:

[ \text{dp}[i] = \max\begin{cases} \text{dp}[i-1], \ \text{dp}[i-2] + A[i], \ \text{dp}[i-3] + A[i-1] + A[i] \end{cases} ]

where the base cases are defined appropriately for \(i=0, 1, 2\).

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains a single integer \(N\) representing the number of treasure chests.
2. The second line contains \(N\) space-separated integers, where the \(i\)-th integer represents the number of gold coins in the \(i\)-th chest.

outputFormat

Output a single integer to standard output (stdout): the maximum number of gold coins that can be collected without opening three consecutive chests.

## sample

1
10

10

</p>