Þér er gefin heiltalnanna af lengd $n$: $a_1, a_2, \dots, a_n$. Þú getur framkvæmt eftirfarandi aðgerð nákvæmlega einu sinni:

• Veldu umröðun $p_1, p_2, \dots, p_n$ á $1, 2, \dots, n$.
• Síðan, fyrir $i$ frá $1$ til $n$ í náttúrulegri röð, framkvæmdu: $$a_{p_i} \leftarrow a_{p_i} + a_{p_i-1} + a_{p_i+1},$$ þar sem $a_0 = 0$ og $a_{n+1} = 0$.

Markmið þitt er að hámarka summu allra staka í rununni eftir að aðgerðinni er lokið.

Inntak

Fyrsta línan inniheldur eina heiltölu $t$ ($1 \le t \le 10^4$), fjölda prófunartilvika. Fyrir hvert prófunartilvik:

Fyrsta línan inniheldur heiltölu $n$ ($1 \le n \le 2 \cdot 10^5$).

Önnur línan inniheldur $n$ heiltölur $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$).

Summa $n$ fer ekki yfir $2 \cdot 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu með heiltölu sem táknar mögulega hámarkssummu allra staka í rununni eftir að aðgerðin hefur verið framkvæmd.

Dæmi

Inntak

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

Úttak

22
85
72
79