题目描述

给定一个长度为 $n$ （ $n$ 是偶数）的序列 $a_1,a_2,a_3 ... a_n$，还有一个初始时为空的队列 $S$。

令 $i$ 依次等于 $1,2,3 ...n$，你需要执行以下两个操作之一：

• 将 $a_i$ 加入当前队列的队尾
• 删除队头元素（执行此操作时，你需要保证队列不为空）

请求出在执行完所有操作后，队列 $S$ 中所有元素之和的最大值。

输入格式

第一行一个正整数 $n$ 。

接下来一行 $n$ 个整数 $a_1,a_2,a_3 ... a_n$ 。

输出格式

一行一个整数表示队列 $S$ 中所有元素之和的最大值。

输入输出样例 #1

输入 #1

6
3 -1 -4 5 -9 2

输出 #1

7

说明/提示

• i=1：$a_1$ 入队，当前队列：[3]
• i=2：$a_2$ 入队，当前队列：[3,-1]
• i=3：出队，当前队列：[-1]
• i=4：$a_4$ 入队，当前队列：[-1,5]
• i=5：出队，当前队列：[5]
• i=6：$a_6$ 入队，当前队列：[5,2]

最终，队列总和 = 5+2 = 7，可以证明，这样操作是最优解

数据范围：

对于 $20\%$ 的数据，$n \leq 20$ 。

对于另外 $10\%$ 的数据，$a_i \geq 0$ 。

对于另外 $10\%$ 的数据，$a_i \leq 0$ 。

对于 $100\%$ 的数据， $1 \le n \leq 10^5，-10^9 \leq a_i \leq 10^9$ ，保证 $n$ 是偶数 。