题目描述

小可正在玩一个消除游戏。

游戏中有一排共 $n$ 个方块，第 $i$ 个方块上写着一个整数 $a_i$。这些整数可能为正，也可能为负。

小可 可以进行任意次操作，每次操作选择以下一种：

1. 选择当前序列中相邻的 $2$ 个方块，将它们一起消除；
2. 选择当前序列中连续的 $3$ 个方块，将它们一起消除。

每次消除后，剩下的方块会按原来的相对顺序拼接起来。

当小可停止操作后，最终得分等于剩余所有方块上的数字之和。如果所有方块都被消除，则最终得分为 $0$。

请你求出小可最多能获得多少分。

输入格式

第一行输入一个整数 $n$，表示初始方块数量。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每个方块上的数字。

输出格式

输出一个整数，表示小可能够获得的最大最终得分。

样例

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

20

5
1 2 3 4 5

15

样例1解释

一种最优操作方式如下：

先消除 $\texttt{-2 -1 -4}$，再消除 $\texttt{-1 -2}$，最后消除 $\texttt{-10 9}$。

剩下的数字为：

1 3 5 -4 15

最终得分为：

可以证明无法得到更高的分数。

数据范围

对于 $30\%$ 的数据，满足 $1 \le n \le 20$。

对于 $60\%$ 的数据，满足 $1 \le n \le 5000$。

对于 $100\%$ 的数据，满足 $1 \le n \le 2 \times 10^5$，$-10^9 \le a_i \le 10^9$。