Maximum Non-Adjacent Balloon Tickets

You are given a sequence of balloons, where each balloon has a number printed on it representing the number of tickets you can obtain by popping it. However, if you pop a balloon, you cannot pop its immediate neighbors. Your task is to determine the maximum number of tickets you can collect by choosing a subset of balloons such that no two selected balloons are adjacent.

Problem Details:

• If there are no balloons, the answer is 0.
• If there is only one balloon, you collect the tickets on that balloon.
• If there are two balloons, you can only choose the one with the higher number of tickets.
• For three or more balloons, use a dynamic programming approach to decide whether to pop a balloon or skip it.

The solution should be implemented such that it reads input from standard input (stdin) and outputs the result to standard output (stdout). All formulas in explanations should use LaTeX formatting if needed.

Consider the recurrence relation for the dynamic programming solution:

$$dp[i] = \max(dp[i-1], dp[i-2] + a_i)$$

where \(a_i\) is the number of tickets on the \(i^{th}\) balloon (1-indexed), and the answer is \(dp[n]\) for \(n\) balloons.

inputFormat

The input is given in the following format:

 n
 a1 a2 ... an

Here, n denotes the number of balloons. If n > 0, the next line contains n space-separated integers where the \(i^{th}\) integer represents the number of tickets on the \(i^{th}\) balloon. If n is 0, no further input is provided.

outputFormat

Output a single integer, which is the maximum number of tickets that can be collected by popping the balloons optimally under the given constraints.

## sample

1
10

10