P16350 「Gensokyo OI Round 1」隙间插曲

::::info[引言：其之二] :::align{center} $\textbf{拉普拉斯之\color{red}眼}\textbf{，注凝万世。}$ ::: :::: 隙间幽深迷离，伸手不见五指，唯一的光源只有那些四处游荡的血色眼瞳。无机质的巨眼在裂隙内上下游走，妖异的红光闪烁着，甚是诡谲。 ——不过，阴森的气氛并没有使完美潇洒的从者感到心悸。毕竟十六夜咲夜再怎么说也是解决过几次异变的人了，于她而言，此地的可怖程度兴许还比不上自家的洋馆吧。 于是，失去了恐吓作用的，所谓「拉普拉斯之魔」的眼睛，能够给咲夜带来的唯一的困扰，便是物理层面上的阻碍了。 ……而显而易见的，物理上的阻碍对于正在解决异变的人来说，是从来都算不上真正的阻碍的。 前路被挡住了就直接将障碍打穿，打不穿障碍就绕道走，“到达另一边”从来都不是什么难事。 也因此，即使身处这样诡异的环境中，女仆长依然有着悠哉悠哉地丢飞刀的余裕。 两把雕着繁杂花纹的银质餐刀破空而出，径直扎进了两颗赤瞳的角膜。吃痛的巨眼随即在空中闭合，随后杳无声息地消失。 紧接着，另一把擦得闪亮的餐刀飞出，仍旧正中靶心。在那之后又是一把，接着又是一把…… 乍一看，以这样的速度，哪怕等到猴年马月也是没有办法开辟一条足够通过隙间的通道的。 ——事实上，这已经很难称之为「清理障碍」了，充其量只能算作是女仆长的「消遣」而已。 不过，既然连时间本身都不过是十六夜咲夜手下的众多侍从之一，那么在完成任务的途中抽出空来消遣一番，又有何不可呢？

#### 原始题面 十六夜咲夜计划用一种特殊的方式丢飞刀，以此作为消遣。 更具体地，她的身周会有一些「拉普拉斯之眼」陆续经过，而后这些眼睛会在她的面前排成一排。 在某一时刻，女仆长会做出决定：向这条队列的第一只眼睛或者最后一只眼睛丢一把飞刀，将其清理掉。 每只眼睛都有自己的硬度，硬度越高的眼睛清理起来越麻烦。 因此，咲夜希望自己清理掉的眼睛硬度尽可能小，也就是最终保留下来的眼睛硬度尽可能大。 而后，咲夜发现，「拉普拉斯之眼」的出现与她的清理操作可以抽象成一个长度为 $n$ 的序列 $a$，其中 $>0$ 的位置表示一只硬度为 $a_i$ 的眼睛排到了队尾，而等于 $0$ 的位置意味着她丢出了一把飞刀。 能够将这个问题抽象化当然是再好不过的了，因为这意味着她可以找到一种更加高效、便捷与系统化的求解方式。 当然，这种求解方式是什么并不重要。完美潇洒的从者当下只想知道，她能够保留下来的眼睛的硬度总和的最大值。 #### 形式化题意 初始时有一个空的双端队列。你需要维护 $n$ 次操作。你已经得到了一个长度为 $n$ 的操作序列 $a_1,\dots,a_n$。 - 如果 $a_i>0$，那么第 $i$ 次操作是在队列的末尾添加一个数 $a_i$。 - 如果 $a_i=0$，那么第 $i$ 次操作是删除操作。 删除操作有两种：删除队列开头的数或删除队列末尾的数。**保证遇到删除操作时队列非空。** 每次执行删除操作时，你可以在两种删除操作中任选其一执行。 你想知道哪一种执行删除操作的方式会使 **最终队列中的所有数之和** 最大。同时，你需要找到这个最大值并输出。

输入共两行。 第一行一个整数 $n$，表示序列 $a$ 的长度。 第二行 $n$ 个非负整数，表示序列 $a$。

输出共一行一个数，表示答案。

### 样例解释 #### 样例 #1 解释 以下是女仆长的最优策略之一： - 进行第一次清理操作时，眼睛序列为 `3 4`。选择清理序列的第一个眼睛，那之后眼睛序列为 `4`。 - 进行第二次清理操作时，眼睛序列为 `4 5 2`。选择清理序列的最后一个眼睛，那之后眼睛序列为 `4 5`。 - 进行第三次清理操作时，眼睛序列为 `4 5 6`。选择清理序列的第一个眼睛，那之后眼睛序列为 `5 6`。 最后眼睛的硬度总和为 $11$。可以证明没有更优的策略了。 ### 数据范围 **本题采用捆绑测试**。 - Subtask $1$（$20\ \text{pts}$）：$n \le 20$。 - Subtask $2$（$10\ \text{pts}$）：不存在 $i$ 满足 $a_i = 0$ 且 $a_{i+1} \not = 0$。 - Subtask $3$（$15\ \text{pts}$）：不存在 $i$ 满足 $a_i = a_{i+1} = 0$。 - Subtask $4$（$10\ \text{pts}$）：$n \le 50$。 - Subtask $5$（$15\ \text{pts}$）：$n \le 200$。 - Subtask $6$（$30\ \text{pts}$）：无特殊限制。 对于所有数据，$1 \le n \le 1000$，$0 \le a_i \le 10^9$。