Taco's Evidence Collection

In this problem, you are given ( n ) evidence items with monetary values ( a_0, a_1, \dots, a_{n-1} ). Your task is to determine the maximum total monetary value Bob can collect, under the constraint that he cannot pick two consecutive evidence items. Formally, you need to select a subset ( S ) of indices such that no two indices in ( S ) are consecutive and maximize ( \sum_{i \in S} a_i ). One way to formulate the solution is by using the recurrence relation: [ dp[i] = \max(dp[i-1],\ a_i + dp[i-2]) ] with appropriate base conditions. This is a classic dynamic programming problem often related to the "House Robber" problem.

inputFormat

The input is given from standard input (stdin) and consists of two lines. The first line contains a single integer ( n ) ( (1 \leq n \leq 10^5) ) representing the number of evidence items. The second line contains ( n ) space-separated integers representing the monetary values of the evidence items.

outputFormat

Output a single integer to standard output (stdout) which is the maximum value Bob can collect without selecting two consecutive items.## sample

1
7

7