Сізге ұзындығы $n$ болатын бүтін сандар тізбегі берілген: $a_1, a_2, \dots, a_n$. Сіз келесі операцияны дәл бір рет орындай аласыз:

• $1, 2, \dots, n$ сандарының $p_1, p_2, \dots, p_n$ алмастыруын таңдаңыз.
• Содан кейін $i$ үшін $1$-ден $n$-ге дейін табиғи ретпен келесіні орындаңыз: $$a_{p_i} \leftarrow a_{p_i} + a_{p_i-1} + a_{p_i+1},$$ мұндағы $a_0 = 0$ және $a_{n+1} = 0$.

Сіздің мақсатыңыз — операция аяқталғаннан кейін тізбектегі барлық элементтердің қосындысын барынша арттыру.

Кіріс деректер

Бірінші жолда бір бүтін сан $t$ ($1 \le t \le 10^4$) — тесттер саны берілген. Әрбір тест үшін:

Бірінші жолда бүтін сан $n$ ($1 \le n \le 2 \cdot 10^5$) берілген.

Екінші жолда $n$ бүтін сан $a_1, a_2, \dots, a_n$ ($-10^8 \le a_i \le 10^8$) берілген.

Барлық тесттер бойынша $n$ қосындысы $2 \cdot 10^5$-нен аспайды.

Шығыс деректер

Әрбір тест үшін операцияны орындағаннан кейін тізбектегі барлық элементтердің мүмкін болатын ең үлкен қосындысын білдіретін бүтін саны бар бір жолды шығарыңыз.

Мысал

Кіріс деректер

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

Шығыс деректер

22
85
72
79