背景

::::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$。

输出格式

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

8
3 4 0 5 2 0 6 0

11

6
3 1 5 2 0 0

7

提示

样例解释

样例 #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$。