คุณจะได้รับลำดับของจำนวนเต็มความยาว $n$: $a_1, a_2, \dots, a_n$

พิจารณาการเลื่อนแบบวน (การหมุน) ที่เป็นไปได้ทั้งหมด $n$ แบบของลำดับนี้ สำหรับตำแหน่งเริ่มต้น $p$ ($1 \le p \le n$) การเลื่อนแบบวนที่สอดคล้องกันคือลำดับ

$$b_1, b_2, \dots, b_n = a_p, a_{p+1}, \dots, a_n, a_1, a_2, \dots, a_{p-1}.$$

สำหรับลำดับที่ถูกเลื่อนนี้ ให้นิยาม ลำดับค่ามากสุดของอุปสรรค (prefix maximum sequence) $c_1, c_2, \dots, c_n$ โดย

$$c_i = \max(b_1, b_2, \dots, b_i) \quad \forall i = 1, 2, \dots, n.$$

เราเปรียบเทียบสองลำดับที่มีความยาวเท่ากันโดยใช้อันดับพจนานุกรมตามปกติ: $c$ จะมีอันดับพจนานุกรมน้อยกว่า $d$ ก็ต่อเมื่อมีดัชนี $i$ ที่ทำให้ $c_1 = d_1, c_2 = d_2, \dots, c_{i-1} = d_{i-1}$ และ $c_i < d_i$

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

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

บรรทัดแรกประกอบด้วยจำนวนเต็มหนึ่งจำนวน $T$ ($1 \le T \le 2 \cdot 10^5$) คือจำนวนชุดทดสอบ

แต่ละชุดทดสอบประกอบด้วยสองบรรทัด:

• บรรทัดแรกประกอบด้วยจำนวนเต็มหนึ่งจำนวน $n$ ($1 \le n \le 5 \cdot 10^5$)
• บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ จำนวน $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)

รับประกันว่าผลรวมของ $n$ ในทุกชุดทดสอบจะไม่เกิน $5 \cdot 10^5$

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

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

ตัวอย่าง

6
5
5 4 3 2 1
4
1 3 1 3
5
1 2 1 3 1
5
2 3 2 1 1
6
1 2 1 3 1 4
6
2 1 3 1 4 1

1 5 5 5 5
1 3 3 3
1 1 2 2 3
1 1 2 3 3
1 2 2 3 3 4
1 2 2 3 3 4