题目背景

连续非空子段的最大和是多少？这很简单，但是如果现在是一个环，并且你还有一次可以翻转区间的机会呢？

描述

你会得到一个长度为 $n$ 的环，分别是 $a_1,a_2,...a_n$，因为是环，所以 $a_1$ 的上一个是 $a_n$ ，$a_n$ 的下一个数是 $a_1$。

你可以选择一段区间，将其翻转，即将 $a_l,a_{l+1}...,a_{r-1},a_r$ 变为 $a_r,a_{r-1},...a_{l+1},a_l$。只能执行一次翻转操作。

请你找到最大的连续非空子段的和为多少。

格式

输入

第一行一个 $n$ ，表示环的大小， $0\leq n\leq 10^5$ 。 第二行 $n$ 个整数，$a_1,a_2,...a_n$，$-10^9\leq a_i \leq 10^9$。

输出

一行一个整数，表示答案。

样例

6
100 -10 -10 22 -10 100

222

样例说明

变为 $100,-10, -10, -10, 22, 100$，最大为 $22+100+100=222$。