题目背景

曹操又听信谗言，采纳铁索连环之策，欲将麾下水师战船连锁以提升战力。不料又一阵妖风袭来，曹操中风再次突发，无法亲自主持连锁事宜。兵贵神速，现请你代为完成 —— 找出战船连锁后能形成的最强战斗力组合！

题目描述

现有 n 条战船沿长江一字排开，第 i 条战船的战斗力为 ai。你可以选择将任意一段相邻的战船用铁索连锁成一个结合体（也可以选择不连锁任何战船，仅取单条战船），该结合体的战斗力为其中所有战船的战斗力之和。请你计算出能形成的结合体的最高战斗力。

输入格式

第一行输入一个整数 n（1 ≤ n ≤ 1e5），表示战船的数量。 第二行输入 n 个整数 a1, a2, ..., an（-100000 ≤ ai ≤ 100000），依次表示每条战船的战斗力。

输出格式

输出一个整数，表示能形成的结合体的最强战斗力。

样例

5
-1 -2 3 -4 5

5

样例解释

所有可能的连锁组合中，仅选择最后一条战斗力为 5 的战船时，能得到最高战斗力 5 。