Maximizing Happiness on the Metro

A subway ring has \( n \) stations numbered from \( 1, 2, \ldots, n \). For each station \( i \) where \( 1 \le i < n \), the next station is \( i+1 \) and for station \( n \) the next is \( 1 \), forming a circle.

Little A starts at any station and rides the subway until he decides to stop at another station. During his ride, he will not revisit any station and will collect \( a_i \) happiness points when passing through station \( i \). His journey must include at least one station. Determine the optimal start and end stations such that the total happiness collected is maximized.

This can be viewed as finding the maximum sum of a contiguous segment in a circular array. Formally, if we have an array \( a_1, a_2, \ldots, a_n \), you need to choose a contiguous segment (which might wrap-around from \( a_n \) back to \( a_1 \)) with maximum sum.

inputFormat

The first line contains an integer \( n \) \( (1 \le n \le 10^5) \) representing the number of stations.

The second line contains \( n \) space-separated integers \( a_1, a_2, \ldots, a_n \) \( (-10^9 \le a_i \le 10^9) \), where \( a_i \) denotes the happiness points collected at station \( i \).

outputFormat

Output a single integer representing the maximum total happiness that Little A can obtain.

sample

5
1 2 -3 4 5

12