Maximum Non-Consecutive Score

You are given a sequence of games where each game has a certain score. Your task is to compute the maximum total score achievable by selecting games such that no two selected games are consecutive. Formally, given an integer \( n \) and an array \( scores \) of length \( n \), determine the maximum sum obtainable by choosing a subset of the scores where no two chosen scores come from consecutive games.

This problem can be modeled using dynamic programming. Let \( dp[i] \) represent the maximum sum obtainable considering games up to the \( i^{th} \) game. Then, the recurrence relation is:

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

with base cases \( dp[0] = scores[0] \) (if \( n \ge 1 \)) and \( dp[1] = \max(scores[0], scores[1]) \) (if \( n \ge 2 \)).

Implement a program that reads the input from standard input and outputs the result to standard output.

inputFormat

The first line contains an integer ( n ) representing the number of games. The second line contains ( n ) space-separated integers, which represent the scores of each game. If ( n = 0 ), the second line will be empty.

outputFormat

Output a single integer: the maximum total score achievable without picking scores from two consecutive games.## sample

5
3 2 7 10 12

22