Sum

 

            The Math teacher gave Gigel a sequence of N integers, from the interval [-10000 , 10000] and asked him to find a substring of this sequence, having the properties that no two elements of the substring are neighbours (that means they are placed on consecutive places) in the initial sequence, and the sum of its elements is as large as possible. Write a program to solve Gigel's problem.

 

Input Data

            The first line of the input file SUM.IN contains the number N of elements of the sequence. The next line will contain the N elements, separated by blanks.

 

Output Data

            In the output file SUM.OUT you will have to write the sum of the substring with the properties described above.

 

Limits

·                     1 <= N <= 200.000

·                     The substring is allowed to be empty, in which case, its sum is 0.

 

Example

SUM.IN               SUM.OUT

7                    16

3 7 5 -1 6 6 2

 

Explaination: You can obtain the sum 16 by choosing the numbers on the positions 1,3,5 and 7.

 

 

Time limit: 0.5 seconds/test case