暂无测试数据。

蒜头幼稚园的 $n$ 名小朋友们排成一列，每个人随机报一个数字 $f_i$，蒜头君站在队首往中间走，白菜君站在队尾往中间走，他们俩走的节奏始终一致，直到相遇为止。

在行走的过程中，他们在某一时刻同时举手，另一时刻同时放下，这中间经过的小朋友会被选中，请问被选中的小朋友们所报数字之和最大可能是多少。

同一名小朋友最多被选中一次，可以不选小朋友，此时和为 $0$ 。

输入格式

输入为 $2$ 行，第一行是一个整数 $n(1 \leq n \leq 10^5)$，为小朋友的人数，第二行是 $n$ 个空格隔开的整数，是每个小朋友报的数字 $f_i(-1000 \leq f_i \leq 1000)$

输出格式

输出为一行，是一个整数，为被选中的小朋友所报数字之和的最大值

数据规模与约定

5
-1 2 9 4 -9

6

8
-3 3 3 -9 9 4 -2 -1

8