ปัญหาไร้เดียงสา - Problème

คุณได้รับลำดับของจำนวนเต็มความยาว $n$: $a_1, a_2, \dots, a_n$ คุณสามารถดำเนินการต่อไปนี้ได้พอดีหนึ่งครั้ง:

เลือกการเรียงสับเปลี่ยน $p_1, p_2, \dots, p_n$ ของ $1, 2, \dots, 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

QOJ.ac