Il Piccolo Pesce Ciano sta giocando a Slay the Spire II e ha scelto il personaggio "La Silenziosa" (Silent).
Il Piccolo Pesce Ciano ora deve combattere contro un "Amico di Battaglia" (Battle Friend). Inizialmente, sia le cariche di "Veleno" (Poison) dell'Amico di Battaglia sia il tuo livello di "Accelerante" (Accelerant) sono pari a $0$. In ciascuno dei successivi $n$ turni, si verificano nell'ordine i seguenti eventi:
Usa "Veleno Mortale" (Deadly Poison): aumenta le cariche di Veleno dell'Amico di Battaglia di $x_i$.
Scegli se usare "Accelerante": scegli se aumentare il tuo livello di Accelerante di $1$.
Attiva l'effetto del Veleno: sia $t$ il tuo livello di Accelerante, ripeti il seguente evento $t$ volte:
- Sia $x$ il numero di cariche di Veleno dell'Amico di Battaglia. Se $x > 0$, infliggi $x$ danni all'Amico di Battaglia e riduci le cariche di Veleno di $1$; altrimenti, se $x = 0$, non accade nulla.
Nota che sia le cariche di Veleno sia il livello di Accelerante si mantengono da un turno all'altro e non scompaiono.
Il Piccolo Pesce Ciano vuole massimizzare il danno totale inflitto all'Amico di Battaglia in questi $n$ turni. Stampa questo valore massimo di danno.
Input
L'input contiene più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T$), che indica il numero di casi di test.
Per ogni caso di test, la prima riga contiene un intero $n$ ($1 \le n \le 5000$).
La seconda riga contiene $n$ interi $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^7$), che indicano il numero di cariche di Veleno aggiunte all'Amico di Battaglia in ciascun turno.
È garantito che la somma di $n$ su tutti i casi di test non superi $10^6$, e che la somma di $n^2$ su tutti i casi di test non superi $10^8$.
Output
Per ogni caso di test, stampa una singola riga contenente un intero che rappresenta il danno totale massimo che può essere inflitto all'Amico di Battaglia in tutti i turni.
Esempio
Input di esempio 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
Output di esempio 1
33 11 750 725