Parade Float Mirror Bonus

A parade organizer has linked n floats together into a single chain, one after another, where n is guaranteed to be even. Each float has an applause score. The organizer pairs floats by mirroring their position in the chain: the 1st float from the front is paired with the 1st float from the back, the 2nd float from the front with the 2nd float from the back, and so on, until every float belongs to exactly one mirrored pair. The mirror bonus of a pair is the sum of the two floats' applause scores. Find the maximum mirror bonus among all n/2 mirrored pairs.

Input format

The first line contains a single even integer n — the number of floats in the chain. The second line contains n integers applause[0], applause[1], ..., applause[n-1] — the applause scores of the floats in chain order, from the front of the parade to the back.

Output format

Print a single integer: the maximum mirror bonus over all n/2 mirrored pairs.

Constraints

• 2 <= n <= 10^5, and n is guaranteed to be even
• 0 <= applause[i] <= 10^5 for every float i

4
5 4 2 1

6

6
4 2 2 3 1 3

7