Rina Loves Shopping

shajia Replay of Ada Lovelace Na...
Limits 1s, 512 MB

Rina loves discounts. Whenever she gets a chance, she goes shopping and looks for the discount offers given by the shops. Recently, she has found a grocery shop that has announced an interesting offer. To avail of that offer, a consumer will need to purchase some products in a particular way.

There will be a row of products in the shop. Each of the products has a special point tag on it. The special point tag of a product indicates a relation between the manufacturing date and expiry date of that particular product. If the date of any product has expired already, the value will be negative. Otherwise, the value will be non-negative. A product that has been manufactured recently will have a bigger value than a product that is not that recent and is going to be expiring soon.

A consumer can buy all the products of the row or they can pick a contiguous sub-sequence of the products from the row. The target for the customers would be to pick the products in such a way that the summation of the special points of the products is maximum. If Rina manages to pick the products in this way, she will get a lifetime discount card. She will have to buy at least one product to be eligible for the offer.

Help Rina to buy products from the shop so that the summation of the points of the chosen products will be maximum.

Input

The first line of the input will contain an integer TT (1T10001≤T≤1000) that denotes the number of test cases. Then for each test case, there will be an integer AA (1A1000001 ≤ A ≤ 100000) — the number of products in that row. Then on the next line, there will be AA integers where each integer ai(a_i(109-10^9aia_i109 10^9 ) denotes the value points of the ithi-th product.

The maximum size of each of the input files will be at most 20MB.

Output

Print the maximum summation of the chosen products from the shop.

Samples

InputOutput
1
5
10 -7 -2 12 30
43
InputOutput
1
6
-9 -45 -25 6 2 1
9

Submit

Login to submit.

Statistics

80% Solution Ratio
naeem4265Earliest, 8M ago
HSTU_TREENITYFastest, 0.0s
user.106537Lightest, 131 kB
jahid_hridoyShortest, 280B
Toph uses cookies. By continuing you agree to our Cookie Policy.