Summe einer Permutation - 문제

Gegeben ist eine Permutation $p$ von $1\sim n$.

Du sollst eine Folge $a$ der Länge $n$ konstruieren, die folgende Bedingungen erfüllt:

Jedes Element der Folge $a$ ist eine positive ganze Zahl, die nicht größer als $n$ ist.
Es gibt kein geordnetes Paar ganzer Zahlen $(l,r)$, für das $1 \le l \le r \le n$ und $\sum\limits_{i=l}^r a_i=\sum\limits_{i=l}^r p_i$ gilt.

Oder gib an, dass keine Lösung existiert.

Eine Permutation von $1\sim n$ ist eine Folge, in der jede positive ganze Zahl, die nicht größer als $n$ ist, genau einmal vorkommt.

Diese Aufgabe enthält mehrere Testfälle.

Die erste Zeile enthält eine ganze Zahl $T$, die die Anzahl der Testfälle angibt.

Anschließend folgen die Testfälle der Reihe nach. Für jeden Testfall gilt:

Die erste Zeile enthält eine ganze Zahl $n$.
Die zweite Zeile enthält $n$ ganze Zahlen, die die gegebene Permutation $p$ beschreiben.

Gib für jeden Testfall eine Zeile aus:

Falls eine Folge $a$ existiert, die die Bedingungen erfüllt, gib $n$ durch Leerzeichen getrennte ganze Zahlen aus, die deine konstruierte Folge $a$ beschreiben.
Falls keine Folge $a$ existiert, die die Bedingungen erfüllt, gib $-1$ aus.

Jede Ausgabe, die die Anforderungen erfüllt, wird akzeptiert.

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

Im Testfall $1$ sind sowohl $\{1,3,3\}$ als auch $\{1,1,3\}$ Folgen $a$, die die Bedingungen erfüllen.

Für Testfall $2$ lässt sich beweisen, dass keine Folge $a$ existiert, die die Bedingungen erfüllt.

Im Testfall $3$ erfüllen neben $\{5,3,2,1,1 \}$ auch Folgen $a$ wie $\{3,4,5,3,2 \}$, $\{1,4,5,3,4 \}$ und $\{5,3,3,4,5\}$ die Bedingungen.

$\sum n$ bezeichnet die Summe der Werte von $n$ innerhalb einer einzelnen Testdatei.

Für alle Daten gilt $1 \le T \le 5000$, $2 \le n \le 10^6$, $\sum n \le 10^6$, und es ist garantiert, dass $p$ eine Permutation von $1\sim n$ ist.

QOJ.ac