Jumlah Permutasi - Problème

Diberikan sebuah permutasi $p$ dari $1\sim n$.

Anda harus membangun barisan $a$ sepanjang $n$ yang memenuhi:

Setiap elemen barisan $a$ merupakan bilangan bulat positif yang tidak lebih dari $n$.
Tidak ada pasangan terurut bilangan bulat $(l,r)$ yang memenuhi $1 \le l \le r \le n$ dan $\sum\limits_{i=l}^r a_i=\sum\limits_{i=l}^r p_i$.

Atau laporkan bahwa tidak ada solusi.

Permutasi dari $1\sim n$ adalah barisan yang memuat setiap bilangan bulat positif yang tidak lebih dari $n$ tepat satu kali.

Soal ini memiliki beberapa kasus uji.

Baris pertama berisi sebuah bilangan bulat $T$ yang menyatakan banyaknya kasus uji.

Selanjutnya diberikan setiap kasus uji secara berurutan. Untuk setiap kasus uji:

Baris pertama berisi sebuah bilangan bulat $n$.
Baris kedua berisi $n$ bilangan bulat yang menyatakan permutasi $p$ yang diberikan.

Untuk setiap kasus uji, cetak satu baris:

Jika ada barisan $a$ yang memenuhi kondisi, cetak $n$ bilangan bulat yang dipisahkan oleh spasi, yang menyatakan barisan $a$ yang Anda bangun.
Jika tidak ada barisan $a$ yang memenuhi kondisi, cetak $-1$.

Semua keluaran yang memenuhi persyaratan akan diterima.

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

Untuk kasus uji $1$, baik $\{1,3,3\}$ maupun $\{1,1,3\}$ merupakan barisan $a$ yang memenuhi kondisi.

Untuk kasus uji $2$, dapat dibuktikan bahwa tidak ada barisan $a$ yang memenuhi kondisi.

Untuk kasus uji $3$, selain $\{5,3,2,1,1 \}$, barisan $a$ seperti $\{3,4,5,3,2 \}$, $\{1,4,5,3,4 \}$, dan $\{5,3,3,4,5\}$ juga memenuhi kondisi.

Misalkan $\sum n$ menyatakan jumlah nilai $n$ dalam satu berkas uji.

Untuk semua data, $1 \le T \le 5000$, $2 \le n \le 10^6$, $\sum n \le 10^6$, dan dijamin bahwa $p$ adalah permutasi dari $1\sim n$.

QOJ.ac