ผลรวมของการเรียงสับเปลี่ยน - Problem

กำหนดการเรียงสับเปลี่ยน $p$ ของ $1\sim n$ ให้

คุณต้องสร้างลำดับ $a$ ที่มีความยาว $n$ และเป็นไปตามเงื่อนไขต่อไปนี้:

สมาชิกแต่ละตัวของลำดับ $a$ เป็นจำนวนเต็มบวกที่ไม่เกิน $n$
ไม่มีคู่อันดับของจำนวนเต็ม $(l,r)$ ที่เป็นไปตาม $1 \le l \le r \le n$ และ $\sum\limits_{i=l}^r a_i=\sum\limits_{i=l}^r p_i$

หรือรายงานว่าไม่มีคำตอบ

ในที่นี้ การเรียงสับเปลี่ยนของ $1\sim n$ หมายถึงลำดับที่จำนวนเต็มบวกทุกจำนวนที่ไม่เกิน $n$ ปรากฏหนึ่งครั้งพอดี

โจทย์นี้มีกรณีทดสอบหลายกรณี

บรรทัดแรกมีจำนวนเต็ม $T$ ซึ่งระบุจำนวนกรณีทดสอบ

จากนั้นเป็นข้อมูลของแต่ละกรณีทดสอบตามลำดับ สำหรับแต่ละกรณี:

สำหรับแต่ละกรณีทดสอบ ให้พิมพ์หนึ่งบรรทัด:

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

คำตอบใด ๆ ที่เป็นไปตามข้อกำหนดจะได้รับการยอมรับ

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

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

สำหรับกรณีทดสอบที่ $1$ ทั้ง $\{1,3,3\}$ และ $\{1,1,3\}$ เป็นลำดับ $a$ ที่เป็นไปตามเงื่อนไข

สำหรับกรณีทดสอบที่ $2$ สามารถพิสูจน์ได้ว่าไม่มีลำดับ $a$ ที่เป็นไปตามเงื่อนไข

สำหรับกรณีทดสอบที่ $3$ นอกจาก $\{5,3,2,1,1 \}$ แล้ว ลำดับ $a$ เช่น $\{3,4,5,3,2 \}$, $\{1,4,5,3,4 \}$ และ $\{5,3,3,4,5\}$ ก็เป็นไปตามเงื่อนไขเช่นกัน

ให้ $\sum n$ แทนผลรวมของ $n$ ในไฟล์ทดสอบหนึ่งไฟล์

สำหรับข้อมูลทั้งหมด $1 \le T \le 5000$, $2 \le n \le 10^6$, $\sum n \le 10^6$ และรับประกันว่า $p$ เป็นการเรียงสับเปลี่ยนของ $1\sim n$

QOJ.ac