Description

Given a circular sequence $a$ of length $n$ (that is, $a_1$ and $a_n$ are adjacent), choose two contiguous, non-overlapping, and non-empty subarrays whose total sum is maximized.

Input Format

The first line contains an integer $n$, the length of the sequence. The second line contains $n$ integers describing the sequence $a$; the $i$-th number is $a_i$.

Output Format

Output a single integer on one line: the maximum possible sum of two subarrays.

7
2 -4 3 -1 2 -4 3

9

Hint

Constraints

For all test points, it is guaranteed that $2 \leq n \leq 2 \times 10^5$ and $-10^4 \leq a_i \leq 10^4$.

Translated by ChatGPT 5