Sinulle annetaan $n$-pituinen kokonaislukujono: $a_1, a_2, \dots, a_n$. Voit suorittaa seuraavan operaation täsmälleen kerran:

• Valitse lukujen $1, 2, \dots, n$ permutaatio $p_1, p_2, \dots, p_n$.
• Suorita sitten luvuille $i$ väliltä $1$ – $n$ luonnollisessa järjestyksessä: $$a_{p_i} \leftarrow a_{p_i} + a_{p_i-1} + a_{p_i+1},$$ missä $a_0 = 0$ ja $a_{n+1} = 0$.

Tavoitteenasi on maksimoida jonon kaikkien alkioiden summa operaation suorittamisen jälkeen.

Syöte

Ensimmäinen rivi sisältää yhden kokonaisluvun $t$ ($1 \le t \le 10^4$), testitapausten lukumäärän. Jokaiselle testitapaukselle:

Ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 2 \cdot 10^5$).

Toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$).

Lukujen $n$ summa ei ylitä arvoa $2 \cdot 10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi rivi, jolla on kokonaisluku, joka ilmaisee jonon kaikkien alkioiden suurimman mahdollisen summan operaation suorittamisen jälkeen.

Esimerkki

Syöte

4
3
1 2 3
4
-1 3 7 6
5
4 1 0 5 2
6
4 -3 7 5 -9 3

Tuloste

22
85
72
79