Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0201 - EQUATOR

   In a galaxy far away, the planet Equator is under attack! The evil gang Galatic Criminal People Cooperation is planning robberies in Equator’s cities. Your help is needed! In order to complete your training for becoming a lord of the dark side you should help them deciding which cities to rob.

   As the name says, the desert planet Equator only can be inhabited on its equator. So the gang lands there at some point and travels into some direction robbing all cities on their way until leaving the planet again.

   But what is still open for them is to decide where to land, which direction to take, and when to leave. Maybe they shouldn’t even enter the planet at all? They do not consider costs for traveling or for running their ship, those are peanuts compared to the money made by robbery!

   The cities differ in value: some are richer, some are poorer, some have better safety functions. So the gang assigned expected profits or losses to the cities. Help them deciding where to begin and where to end their robbery to maximize the money in total when robbing every city in between.

Input

   The input starts with the number of test cases T 30. Each test case starts a new line containing the number of cities 1 n 1 000 000. In the same line n integers ci follow. Each ci (0 i < n,−1000 ci +1000) describes the money obtained when robbing city i, a negative ci describes the amount of money they would lose.

Output

   For each test case print one integer describing the maximum money they can make in total.

Examples

stdin

stdout

1

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

6
14
0


Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2014-10-08
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PYPY3 PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.German (GCPC) 2014.E

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.