Question
Maximize Gold Heist
In a distant kingdom, there was a wealthy merchant named Alex who owned N treasure houses, each filled with gold pots. The treasure houses were lined up in a straight row and numbered from 1 to N. One night, while Alex was away attending a grand feast, a clever thief saw the perfect chance to strike. However, the thief had to be smart to avoid the kingdom’s guards. He could only rob a single, continuous segment of treasure houses and had to take the same number of gold pots from each house he targeted.
The thief now seeks your help to figure out the maximum number of gold pots he can steal in one go without getting caught by the guards. Can you help him plan the heist for the greatest reward?
The thief now seeks your help to figure out the maximum number of gold pots he can steal in one go without getting caught by the guards. Can you help him plan the heist for the greatest reward?
Input
The first line of the input contains an integer T, denoting the number of test cases.
The first line of each test case contains a single integer N denoting the number of factories.
The second line of each test case contains N space-separated integers :
a[1], a[2],. a[n] denotes the number of gold pots in ith factories.
Constraints
1 ≤ T ≤ 5
1 ≤ N ≤ 106
0 ≤ A[i] ≤ 1012
The first line of each test case contains a single integer N denoting the number of factories.
The second line of each test case contains N space-separated integers :
a[1], a[2],. a[n] denotes the number of gold pots in ith factories.
Constraints
1 ≤ T ≤ 5
1 ≤ N ≤ 106
0 ≤ A[i] ≤ 1012
Output
Output exactly T lines. The ith line should contain a single integer, i.e the answer for Ith test case.
Example
Sample Input
2
5
2 4 3 2 1
6
3 0 5 4 4 4
Sample Output
8
16
Explanation
In the first test case thief will steal 2 sacks from each warehouse from 1 to 4.
2
5
2 4 3 2 1
6
3 0 5 4 4 4
Sample Output
8
16
Explanation
In the first test case thief will steal 2 sacks from each warehouse from 1 to 4.