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.