On vous donne une permutation $p$ de $1\sim n$.
Vous devez construire une suite $a$ de longueur $n$ qui satisfait les conditions suivantes :
- Chaque élément de la suite $a$ est un entier strictement positif inférieur ou égal à $n$.
- Il n’existe aucun couple ordonné d’entiers $(l,r)$ tel que $1 \le l \le r \le n$ et $\sum\limits_{i=l}^r a_i=\sum\limits_{i=l}^r p_i$.
Ou bien indiquez qu’il n’existe aucune solution.
Une permutation de $1\sim n$ est une suite dans laquelle chaque entier strictement positif inférieur ou égal à $n$ apparaît exactement une fois.
Entrée
Ce problème comporte plusieurs cas de test.
La première ligne contient un entier $T$, qui indique le nombre de cas de test.
Les cas de test sont ensuite donnés dans l’ordre. Pour chaque cas de test :
- La première ligne contient un entier $n$.
- La deuxième ligne contient $n$ entiers représentant la permutation donnée $p$.
Sortie
Pour chaque cas de test, affichez une ligne :
- S’il existe une suite $a$ satisfaisant les conditions, affichez $n$ entiers séparés par des espaces, représentant la suite $a$ que vous avez construite.
- S’il n’existe aucune suite $a$ satisfaisant les conditions, affichez $-1$.
Toute sortie satisfaisant les exigences sera acceptée.
Exemples
Entrée 1
4 3 3 2 1 2 1 2 5 4 2 1 5 3 7 5 7 3 1 2 4 6
Sortie 1
1 3 3 -1 5 3 2 1 1 2 3 5 4 6 3 1
Remarque
Pour le cas de test $1$, les suites $\{1,3,3\}$ et $\{1,1,3\}$ sont toutes deux des suites $a$ satisfaisant les conditions.
Pour le cas de test $2$, on peut démontrer qu’il n’existe aucune suite $a$ satisfaisant les conditions.
Pour le cas de test $3$, outre $\{5,3,2,1,1 \}$, des suites $a$ telles que $\{3,4,5,3,2 \}$, $\{1,4,5,3,4 \}$ et $\{5,3,3,4,5\}$ satisfont également les conditions.
Contraintes
Soit $\sum n$ la somme des valeurs de $n$ dans un seul fichier de test.
Pour toutes les données, $1 \le T \le 5000$, $2 \le n \le 10^6$, $\sum n \le 10^6$, et il est garanti que $p$ est une permutation de $1\sim n$.