Hoán Vị Yêu Thích Của FJ

Farmer John có một hoán vị $p$ độ dài $N$ ($2\le N\le {10}^5$). Farmer Nhoj đã tháo rời hoán vị và tạo ra gợi ý bằng quy trình sau:

Gọi $p_1^{\prime },p_2^{\prime },\dots ,p_m^{\prime }$ là các phần tử còn lại (ban đầu $m=N$). Lặp lại cho đến khi còn 1 phần tử:

• Nếu $p_1^{\prime }>p_m^{\prime }$: ghi ra $p_2^{\prime }$ và xóa $p_1^{\prime }$
• Ngược lại ($p_1^{\prime }\le p_m^{\prime }$): ghi ra $p_{m-1}^{\prime }$ và xóa $p_m^{\prime }$

Quy trình tạo ra $N-1$ giá trị gợi ý $h_1,h_2,\dots ,h_{N-1}$.

Cho dãy $h$, tìm hoán vị $p$ nhỏ nhất theo thứ tự từ điển thỏa mãn gợi ý, hoặc in $-1$ nếu không tồn tại.

Dữ liệu vào

• Dòng 1: Số nguyên $T$ -- số test case ($1\le T\le 10$)
• Mỗi test case:
  • Dòng 1: Số nguy��n $N$
  • Dòng 2: $N-1$ số nguyên $h_1,h_2,\dots ,h_{N-1}$ ($1\le h_i\le N$)

Dữ liệu ra

Với mỗi test case, in hoán vị nhỏ nhất theo thứ tự từ điển, hoặc $-1$ nếu không khả thi.

Ràng buộc

• $2\le N\le {10}^5$
• $1\le T\le 10$
• Test 2: $N\le 8$
• Test 3-6: $N\le 100$

Ví dụ