Description
The description provided for this problem:
The Serpent has led a C.H.I.M.E.R.A. project to build a new type of AI system, one with a series of “smart bricks” plugged together all in a row creating a super fast and super powerful AI with a goal of reaching artificial curiosity and creativity – to come up with better ways take over Mars!.
After a successful mission, Agent Ω has stolen a chain of these AI bricks and wants to take it apart to study it. The problem is that once any brick is removed, its two neighbors both self-destruct. As such, Agent Ω must determine ahead of time which bricks to break into and no two can be next to each other.
Agent Ω figures out how fast each smart brick is and wants to collect the fastest possible set of them. You must help her choose which subset of bricks she will target such that she maximizes total brick speed (the sum of bricks chosen) without chosing any two that are neighbors.
Given a series of N smart bricks where brick i, in order, has speed Si , determine the maximum total speed that can be obtained.
Input Format
The first line provides N, the number of smart bricks in the row.
The second line has N values, separated by spaces, indicating the speed of each smart brick (S0 through SN-1 ).
Constraints
1 ≤ N ≤ 106
1 ≤ Si ≤ 1010
Output Format
A single number indicating the maximum total speed possible.
Example 0
Sample Input
5
2 10 1 3 10
Sample Output
20
Explanation
There are five smart bricks, with speeds of 2, 10, 1, 3, and 10, respectively.
If Agent Ω breaks into the second and fifth bricks, we will have a total speed of 20 (no other legal combination can produce more than 20).
Example 1
Sample Input
5
20 10 1 10 20
Sample Output
41
Explanation
There are five smart bricks, with speeds of 20, 10, 1, 10, and 20, respectively.
If Agent Ω breaks into the first, middle, and last bricks, we will have a total speed of 41 (no other legal combination can produce more than 41).
