A ring of n sensors is arranged in a circle. Sensor i reports an integer reading (possibly negative). A circular window is a non-empty run of consecutive sensors that may wrap around: after the last sensor it continues at the first. A window uses each sensor at most once, so its length is between 1 and n.
Return the maximum possible total reading over all circular windows.
Useful idea: the best window either stays within the array (a standard maximum subarray) or wraps around, and a wrapping window is exactly the whole ring minus a contiguous middle block. So the wrapping best equals total - (minimum subarray sum). Handle the case where every reading is negative separately, since then the wrapping formula would select an empty middle block.
Input format
Line 1: an integer n, the number of sensors.
Line 2: n space-separated integers, the readings around the ring (present whenever n >= 1).
Output format
A single integer: the maximum total reading over all non-empty circular windows.
Constraints
- 1 <= n <= 100000
- -1000000 <= each reading <= 1000000
- The window must contain at least one sensor and each sensor at most once.