Litli Blágræni Fiskurinn er að spila Slay the Spire II og hefur valið persónuna „Hin Þögla“ (Silent).

Litli Blágræni Fiskurinn þarf nú að berjast við „Bardagavin“ (Battle Friend). Í upphafi eru bæði „Eitur“-staflar (Poison) Bardagavinarins og „Hröðunar“-stig (Accelerant) þitt jöfn $0$. Í hverri af næstu $n$ umferðum gerast eftirfarandi atburðir í þessari röð:

1. Nota „Banaeitur“ (Deadly Poison): hækkaðu Eitur-stafla Bardagavinarins um $x_i$.

2. Velja hvort nota eigi „Hröðun“: veldu hvort þú viljir hækka Hröðunar-stigið þitt um $1$.

3. Virkja áhrif Eiturs: látum Hröðunar-stigið þitt vera $t$ og endurtaktu eftirfarandi atburð $t$ sinnum:

   • Látum Eitur-stafla Bardagavinarins vera $x$. Ef $x > 0$, veldurðu Bardagavininum $x$ stigum af skaða og lækkar Eitur-staflana um $1$; annars, ef $x = 0$, gerist ekkert.

Athugaðu að bæði Eitur-staflarnir og Hröðunar-stigið haldast milli umferða og hverfa ekki.

Litli Blágræni Fiskurinn vill hámarka heildarskaðann sem Bardagavinurinn verður fyrir í þessum $n$ umferðum. Vinsamlegast prentaðu út þennan hámarksskaða.

Inntak

Inntakið inniheldur mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur heiltölu $T$ ($1 \le T$), sem táknar fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan heiltölu $n$ ($1 \le n \le 5000$).

Önnur línan inniheldur $n$ heiltölur $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^7$), sem tákna fjölda Eitur-stafla sem bætast við Bardagavininn í hverri umferð.

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $10^6$, og að summa $n^2$ yfir öll prófunartilvik fari ekki yfir $10^8$.

Úttak

Fyrir hvert prófunartilvik skal prenta út eina línu sem inniheldur heiltölu sem táknar hámarks heildarskaða sem hægt er að valda Bardagavininum í öllum umferðum.

Dæmi

Inntaksdæmi 1

4
5
1 1 0 3 7
3
0 3 2
9
9 9 8 2 4 4 3 5 3
13
1 1 4 5 1 4 1 9 1 9 8 1 0

Úttaksdæmi 1

33
11
750
725