Search for the maximum subarray sum after a cyclic shift

Kotlin Hard loops

Task «Search for the maximum subarray sum after a cyclic shift»

Given an array of integers. It is allowed to perform exactly one cyclic shift to the left (the first element becomes the last) or to the right (the last element becomes the first) any number of times, but not exceeding the length of the array. After that, it is necessary to find the maximum sum of a contiguous subarray (using Kadane's algorithm). The goal is to determine the largest possible sum that can be obtained after performing one cyclic shift. If the array is empty, output 0.

Input Format

First line: integer N (1 ≤ N ≤ 10^6) — the length of the array. Second line: N integers separated by spaces (each modulo ≤ 10^9).

Output Format

One integer — the maximum sum of a subarray after one cyclic shift.

Examples

Example 1

INPUT

4
-1 -2 -3 -4

OUTPUT

-1

main.kt