- Time limit: 1.00 s
- Memory limit: 512 MB
Given a sequence of integers, find the largest sum of a consecutive subsequence of odd length.
Input
The first line of input contains n, the length of the sequence. The second line containts n integers, a_1, a_2, \ldots, a_n, the elements of the sequence.
Output
Print the largest sum of a consecutive subsequence of odd length.
Constraints
- 1 \le n \le 10^6
- -10^9 \le a_i \le 10^9
Example
Input:
4 8 -7 9 1
Output:
10
The largest sum is given by the subsequence 8 -7 9
.