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.