Non-Consecutive Token Collection

Alex is playing a game where he collects tokens arranged in a row. Each token bears an integer (which can be positive or negative). He can choose any subset of tokens with the restriction that no two consecutive tokens are selected. The score is defined as the sum of the values on the selected tokens. If all tokens are negative, Alex may opt to not select any tokens, resulting in a score of 0.

A typical dynamic programming solution uses the recurrence relation \(dp[i]=\max(dp[i-1],\;dp[i-2]+tokens[i])\), which ensures that for each token, Alex considers either skipping it or picking it (while being careful with the consecutive selection rule).

inputFormat

The input consists of two lines. The first line contains a single integer \(n\) \((1 \le n \le 10^5)\), the number of tokens. The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\) representing the value on each token.

outputFormat

Output a single integer representing the maximum score Alex can achieve by selecting tokens with the rule that no two consecutive tokens are chosen.

4
1 2 9 4

10