以下是翻译结果：具有循环移位的最大子数组和

PHP Hard arrays

任务 «以下是翻译结果：具有循环移位的最大子数组和»

给定一个整数数组。需要找到在恰好应用一次循环左移任意位置（从0到N-1）后，子数组（连续元素序列）的最大和。如果移位后子数组可以为空，则空子数组的和视为0。若所有元素均为负数，子数组必须至少包含一个元素。限制条件：数组长度从1到10^5，元素范围从-10^9到10^9。

第一行包含一个整数 N (1 ≤ N ≤ 100000) — 数组的大小。第二行包含 N 个整数 — 数组的元素。

一个整数——经过一次循环左移后子数组的最大和。

输入

5

输出

10

输入

-3

输出

-6

main.php