คุณได้รับการเรียงสับเปลี่ยน $p$ หนึ่งชุดที่มีความยาว $n$ สำหรับช่วงย่อยต่อเนื่องของ $p$ นิยามค่าใช้จ่ายของมันให้เป็นความยาวของลำดับย่อยเพิ่มขึ้นที่ยาวที่สุดของช่วงย่อยนี้ สำหรับการแบ่งส่วนของ $p$ ออกเป็นช่วงย่อยต่อเนื่องที่ไม่ทับซ้อนกัน นิยามค่าใช้จ่ายของมันให้เป็นผลรวมของค่าใช้จ่ายของช่วงย่อยเหล่านี้

นิยาม $a_k$ ให้เป็นค่าใช้จ่ายที่มากที่สุดในบรรดาการแบ่งส่วนของ $p$ ออกเป็น $k$ ช่วงย่อยต่อเนื่องที่ไม่ว่างและไม่ทับซ้อนกัน

คุณต้องหาค่า $a_k$ สำหรับแต่ละ $k$ ตั้งแต่ $1$ ถึง $n$

ข้อมูลนำเข้า

ข้อมูลนำเข้าประกอบด้วยหลายกรณีทดสอบ บรรทัดแรกประกอบด้วยจำนวนเต็มเพียงตัวเดียวคือ $t$ ($1 \le t \le 10^3$) แทนจำนวนกรณีทดสอบ จากนั้นเป็นคำอธิบายของแต่ละกรณีทดสอบ

บรรทัดแรกของแต่ละกรณีทดสอบประกอบด้วยจำนวนเต็ม $n$ ($1 \le n \le 10^5$)

บรรทัดที่สองประกอบด้วยจำนวนเต็มที่แตกต่างกัน $n$ จำนวน คือ $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$) ซึ่งร่วมกันกำหนดการเรียงสับเปลี่ยนของ $1, 2, \dots, n$

ผลรวมของ $n$ จากทุกกรณีทดสอบไม่เกิน $10^5$

ข้อมูลส่งออก

สำหรับแต่ละกรณีทดสอบ ให้พิมพ์ $a_1, a_2, \dots, a_n$ ในบรรทัดเดียว

ตัวอย่าง

ข้อมูลนำเข้า 1

5
5
1 2 3 4 5
5
5 4 3 2 1
8
2 4 1 3 6 5 8 7
9
3 2 1 6 5 4 9 8 7
1
1

ข้อมูลส่งออก 1

5 5 5 5 5
1 2 3 4 5
4 6 7 8 8 8 8 8
3 4 5 6 7 8 9 9 9
1

หมายเหตุ

พิจารณากรณีทดสอบที่สามซึ่งมีการเรียงสับเปลี่ยน $p = [2, 4, 1, 3, 6, 5, 8, 7]$:

• สำหรับ $k = 1$ คำตอบก็คือความยาวของลำดับย่อยเพิ่มขึ้นที่ยาวที่สุดใน $p$ ซึ่งคือ $a_1 = 4$
• สำหรับ $k = 2$ การแบ่งส่วนออกเป็น $[2, 4]$ และ $[1, 3, 6, 5, 8, 7]$ มีค่าใช้จ่ายมากที่สุดคือ $a_2 = 2 + 4 = 6$
• สำหรับ $k = 3$ การแบ่งส่วนออกเป็น $[2, 4]$, $[1, 3, 6]$ และ $[5, 8, 7]$ มีค่าใช้จ่ายมากที่สุดคือ $a_3 = 2 + 3 + 2 = 7$
• สำหรับ $k = 4$ การแบ่งส่วนออกเป็น $[2, 4]$, $[1, 3, 6]$, $[5, 8]$ และ $[7]$ มีค่าใช้จ่ายมากที่สุดคือ $a_4 = 2 + 3 + 2 + 1 = 8$
• สำหรับ $k > 4$ เห็นได้ง่ายว่า $a_k = 8$