Maximum Coin Sum

Harold is on a quest to collect coins arranged in a straight line. He can start at any coin position and then proceed in a single direction (either left or right) without changing direction. The coins can have both positive and negative values. Your task is to determine the maximum sum of coin values Harold can collect when he chooses his starting point and direction optimally.

Mathematically, for a list of coins represented as \(a_1, a_2, \ldots, a_N\), the maximum sum is defined as:

[ \text{max_sum} = \max_{1 \leq i \leq N} \max\left{ \sum_{j=i}^{N} a_j, ; \sum_{j=i}^{1} a_j \right}]

Note that when moving left, Harold collects coins in reverse order and when moving right, he collects coins in the natural order.

inputFormat

The first line of input contains an integer (T) representing the number of test cases. For each test case, the first line contains an integer (N) denoting the number of coins. The next line contains (N) space-separated integers representing the value of each coin.

outputFormat

For each test case, print a single line containing the maximum sum of coin values that Harold can collect.## sample

2
5
1 -2 3 4 -1
3
-1 -2 -3

7
-1