有这样两兄妹，哥哥叫大宝，妹妹叫小美。
因为疫情的关系，妈妈嘱咐他俩要乖乖待在家里，为了打发时间他们发明了一种全新的抓娃娃游戏。
有 n 个娃娃排成一排，编号 1…n ，每个娃娃有个价值分，大宝和小美各有一次抓娃娃的机会，规则是这样的：在剩下的娃娃中，取连续的若干个。大宝和小美当然想得到尽可能多的价值分，但有些娃娃价值分是负数，并不是拿越多越好。
妈妈怕他俩因玩游戏伤了和气，于是改动了规则：大宝和小美同时取，各取连续的一段，这两段是要完全错开的，例如大宝取从第 x1 到 y1 （x1≤y1) ，小美取从 x2 到 y2  (x2≤y2) ，那么 y1<x2 和 y2<x1 两个中必然有一个成立 ，求在所有方案中两人能拿到的最大价值分总和。
如果成功了大宝和小妹将得到妈妈的奖励，否则罚做一个小时的家务。
两人前来求助，你能帮助他们吗？

第一行一个整数 n ，表示娃娃个数。
第二行 n 个整数 ai ，表示每个娃娃的得分。

一个整数，表示如果获得了成功，大宝和小美的总得分。

对于 30% 的数据满足 2≤n≤100 
对于 60% 的数据满足 2≤n≤30000 
对于 100% 的数据满足 2≤n≤1000000 
对于 100% 的数据满足 −1000≤ai≤1000

信息未来