该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一个长度为 $n$ 的数组 $a$，但是 $a$ 中可能存在一些负数会使得 $a$ 的总和不够大。现在你希望总和尽可能大，你可以做以下两种操作任意次（也可以不做）：

• 选择两个相邻的数字 $a_i$ 和 $a_{i+1}$ （$1\leq i<n$），将其删除，其余数字顺次拼接起来。（换句话说数组 $a$ 会变为 $(a_1,a_2,\cdots,a_{i-1},a_{i+2},\cdots,a_n)$）。
• 选择三个连续的数字 $a_i,a_{i+1},a_{i+2}$ （$1\leq i\leq n-2）$，将其删除，其余数字顺次拼接起来。

现在你需要求出数组 $a$ 最大的总和可能是多少。

输入格式

第一行输入一个整数 $n$。

接下来一行输入 $n$ 个空格隔开的整数分别代表 $a_1,a_2,\cdots,a_n$。

输出格式

对于每一组数据，在单独一行中输出最终剩余元素的可能最大值。

12
1 3 -2 -1 -4 -1 -2 5 -4 15 -10 9

20

5
1 2 3 4 5

15

1
1

1

提示

样例 1 解释

在第一组数据中，序列 $a$ 原本为 [1, 3, -2, -1, -4, -1, -2, 5, -4, 15, -10, 9]

• 首先可以删除 $-2,-1$，序列变为 [1, 3, -4, -1, -2, 5, -4, 15, -10, 9]。

• 然后删除 $-4,-1,-2$ 可以得到 [1, 3, 5, -4, 15, -10, 9]。

• 然后删除 $-10,9$ 可以得到 [1, 3, 5, -4, 15]。

此时序列的总和最大为 $20$。

数据范围

对于 $100\%$ 的数据，$1\leq n\leq 2\cdot 10^5$，$-10^9\leq a_i\leq 10^9$。

• 子任务 1（30 分）：保证 $a_i>0$
• 子任务 2（30 分）：保证 $n\leq 20$
• 子任务 3（40 分）：没有特殊限制。