Maximum Sequence Sum After Merging

You are given a sequence of n integers. You are allowed to merge exactly one pair of consecutive elements into a single element, where the new element is the sum of the two merged elements. Note that merging does not change the overall sum of the sequence, i.e. \(S = \sum_{i=1}^{n} a_i\). For the case when n = 1, the sequence remains unchanged.

Your task is to compute the maximum possible sum of the sequence after performing this merging operation.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), the number of elements in the sequence. The second line contains n space-separated integers \(a_1, a_2, \dots, a_n\) where each \(a_i\) is in the range of \(-10^9\) to \(10^9\).

outputFormat

Output a single integer which is the maximum possible sum of the new sequence after performing the merge operation exactly once (or leaving it unchanged if n = 1).

5
1 2 3 4 5

15