Decoração de Interiores

Marta é um exímia decoradora de interiores que atingiu fama e sucesso devido seu modo peculiar de trabalho: uma vez identificados os $N$ itens que comporão a decoração e as $N$ localizações para estes itens, ela avalia todas as $N!$ possibilidades de posicionamento destes objetos, uma a uma!

Após perder uma série de funcionários, que não aguentavam a estressante rotina do “tira daqui, coloca ali”, Marta encomendou um software que simulava o interior, os itens e as localizações em modelos tridimensionais, e apresentava todas estas possibilidades em sequência. Como Marta tem pouca familiaridade com computadores, ela fez a exigência que o programa deveria ter apenas um único botão: para frente!

Neste software, cada objeto e cada localização recebe um identificador inteiro entre 1 e $N$, e uma possibilidade (configuração) do ambiente é armazenada em uma lista de $N$ inteiros, onde o $i$-ésimo número $n_i$ significa que o objeto $n_i$ ocupa a localização $i$. Por exemplo, a configuração $\lbrace 4, 2, 1, 3\rbrace$ significa: objeto 4 na localização 1, objeto 2 na localização 2, objeto 1 na localização 3 e objeto 3 na localização 4. As configuração são geradas e apresentadas na ordem lexicográfica, isto é, ordenadas de forma ascendente.

Marta logo se adaptou à nova tecnologia e conseguiu ampliar seu sucesso e renome, pois conseguia resultados mais rapidamente do que nunca. Porém, acabou por sentir falta de um recurso bastante simples: retornar à configuração anterior pois, de vez em quando, ela apertava inadvertidamente o botão avançar!

Auxilie Marta adicionando esta funcionalidade no software de simulação.

Entrada

A entrada é composta por duas linhas: a primeira contém o inteiro $N$ $(1\leq N\leq 2\times 10^5)$, que indica o número de objetos e localizações disponíveis.

A segunda linha da entrada contém $N$ inteiros $n_i$ $(1 \leq n_i \leq N)$, separados por um espaço em branco, indicando a configuração atual do ambiente.

Saída

Imprima, em uma linha, os $N$ inteiros que representam a configuração que antecedia a configuração dada. Caso a configuração dada seja a configuração inicial do software, imprima o valor $-1$.

Exemplo de entrada 1

3
3 1 2

Exemplo de saída 1

2 3 1

Exemplo de entrada 2

4
1 2 3 4

Exemplo de saída 2

-1

Exemplo de entrada 3

5
2 4 1 3 5

Exemplo de saída 3

2 3 5 4 1

Exemplo de entrada 4

10
7 8 2 3 4 1 6 5 10 9

Exemplo de saída 4

7 8 2 3 4 1 6 5 9 10