Maximum Items Collection

In this problem, Alex visits a line of N stalls where each stall contains a number of items. He can start at any stall and collect items by moving to both the left and right continuously. The goal is to determine the maximum number of items that Alex can collect. Formally, if we denote the number of items at each stall by \(a_0, a_1, \dots, a_{N-1}\), then if Alex starts at stall \(i\) he collects all items from stalls \(0\) to \(i\) and from stalls \(i\) to \(N-1\) (counting stall \(i\) only once). Hence the total number of items collected when starting at stall \(i\) is given by:

[ S_i = \sum_{j=0}^{i} a_j + \sum_{j=i}^{N-1} a_j - a_i, ]

Your task is to compute \(\max_{0 \le i < N} S_i\).

Note: When \(N=0\) (i.e. there are no stalls), the result is 0.

inputFormat

The first line contains an integer \(N\) denoting the number of stalls. If \(N > 0\), the second line contains \(N\) space-separated integers representing the number of items at each stall.

outputFormat

Output a single integer, the maximum number of items Alex can collect.

5
4 2 3 5 1

15