Make More Money

shariful_islam BUET Inter University Pro...
Limits 1s, 512 MB

You, the great businessman of TEUB, arrived at ESC land which consists of NN cities numbered from 1 to NN. You are currently at city 1. For each city ii, you arrive at (including your current city) in ESC land, you do some business and make profit aia_i. The profit can be negative which means you have lost ai|a_i| amount of money in your business.But there is a special rule for travelling ESC land:

  1. First you can go from your current location i.e. city 1 to city ii through the path 1,2,3,,i1, 2, 3, \cdots, i ( 1iN1 \le i \le N ).

  2. Then you can go from city ii to city jj through the path i,i1,i2,,ji, i-1, i-2, \cdots, j ( 1j<i1 \le j < i ).

So, your profit will be a1+a2+a3+...+ai+ai1+ai2++aja_1+a_2+a_3+...+a_i+a_{i-1}+a_{i-2}+\cdots + a_j

Note that you may stay at city 1 and you may also choose not to go to reverse direction (i.e. direction to which city index decreases).

Find out maximum profit you can achieve.

Input

First line will be number of test cases TT

For each test case:

In the first line, the number of cities NN will be given.

Then there will be NN integers a1,a2,,aNa_1, a_2, \cdots, a_N where aia_i denotes achievable profit from city ii at a time.

Constraints

1T101 \le T \le 10

1N1051 \le N \le 10^5

104ai104-10^4 \le a_i \le 10^4

Over all test cases, N2105\sum{N} \le 2*10^5

Output

For each test case, print one line containing maximum possible profit you can gain.

Sample

InputOutput
4
1
4
2
4 -2
3
5 2 -10
4
-1 3 -2 4
4
6
12
5

Optimal paths for the 4 testcases are:

  1. path: 11, profit: 44

  2. path: 1211 \to 2 \to 1, profit: 4+(2)+4=64 + (-2) + 4 = 6

  3. path: 1211 \to 2 \to 1, profit: 5+2+5=125 + 2 +5 = 12

  4. path: 1234321 \to 2 \to 3 \to 4 \to 3 \to 2, profit: (1)+3+(2)+4+(2)+3=5(-1)+3+(-2)+4+(-2)+3=5

Submit

Login to submit.

Statistics

67% Solution Ratio
Jarif_RahmanEarliest, 5d ago
Program28Fastest, 0.0s
Program28Lightest, 131 kB
Fahim9090Shortest, 421B
Toph uses cookies. By continuing you agree to our Cookie Policy.