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