Задачи
Восстановление перестановки
Восстановление перестановки
Сегодня в школе Кристофер изучал последовательности и перестановки. Напомним, что \textit{перестановкой} чисел от \textbf{1} до \textbf{n} называется последовательность \textbf{a_1}, ..., \textbf{a_n}, в которую каждое из указанных чисел входит ровно один раз.
Особенно ему понравились следующие определения:
\begin{itemize}
\item \textit{Спуском} в позиции \textbf{i} в перестановке <\textbf{a_1}, \textbf{a_2}, ..., \textbf{a_n}> называют такую ситуацию, что \textbf{a_i} > \textbf{a_\{i+1\}};
\item \textit{Неподвижной точкой} в позиции \textbf{i} в перестановке <\textbf{a_1}, \textbf{a_2}, ..., \textbf{a_n}> называют такой элемент \textbf{a_i}, что \textbf{a_i} = \textbf{i}.
\end{itemize}
Узнав эти определения, он придумал собственную перестановку и назвал её \textit{перестановкой Робина}.
Назовем перестановку \textbf{A} = <\textbf{a_1}, \textbf{a_2}, ..., \textbf{a_2n}> из \textbf{2n} натуральных чисел от \textbf{1} до \textbf{2n} \textit{перестановкой Робина}, если выполнены следующие условия:
\begin{itemize}
\item \textbf{A} имеет ровно \textbf{n} спусков, и все его спуски находяться на нечетных позициях (то есть \textbf{a_\{2i-1\}} > \textbf{a_2i} < \textbf{a_\{2i+1\}} для всех \textbf{i});
\item \textbf{A} имеет ровно \textbf{n} неподвижных точек.
\end{itemize}
Например, перестановка <\textbf{3}, \textbf{2}, \textbf{6}, \textbf{4}, \textbf{5}, \textbf{1}> является \textit{перестановкой Робина}.
Кристофер решил поделиться своим открытием с Кроликом. Узнав о \textit{перестановке Робина}, Кролик придумал следующее преобразование: удалим все неподвижные точки в последовательности и превратим оставшийся вектор в перестановку, заменив оставшиеся числа на количество элементов, не превосходящих его в перестановке. Например, преобразование перестановки <\textbf{3}, \textbf{2}, \textbf{6}, \textbf{4}, \textbf{5}, \textbf{1}> дает <\textbf{3}, \textbf{2}, \textbf{6}, \textbf{4}, \textbf{5}, \textbf{1}> → <\textbf{3}, \textbf{6}, \textbf{1}> → <\textbf{2}, \textbf{3}, \textbf{1}>.
Кристофер теперь хочет получить по преобразованной перестановке \textit{перестановку Робина}.
\InputFile
В первой строке входного файла дано \textbf{n} - число элементов в преобразованной перестановке (\textbf{1} ≤ \textbf{n} ≤ \textbf{100000}). Во второй строке входного файла дано \textbf{n} натуральных чисел - преобразованная перестановка.
\OutputFile
Если нет решения, вывести \textbf{-1} в первой строке выходного файла. Если существует \textit{перестановка Робина}, то вывести её. Если несколько решений, то вывести любую \textit{перестановку Робина}.
Входные данные #1
3 2 3 1
Выходные данные #1
3 2 6 4 5 1