Группе студентов наскучило носить одну и ту же обувь каждый день, поэтому они решили обменяться обувью. В этой задаче пара обуви неразделима и понимается как один объект.
В группе \(n\) студентов, и вам дан массив \(s\) в неубывающем порядке, где \(s_i\) — размер обуви \(i\)-го студента. Обмен обувью называется корректным, если никто не получит свою обувь, и каждый студент получит обувь не меньшего размера, чем его собственная.
Вам нужно вывести перестановку \(p\) целых чисел \(\{1,2,\ldots,n\}\), описывающую корректный обмен обувью: \(i\)-й студент получит обувь \(p_i\)-го студента (\(p_i \ne i\)). Если решения не существует, выведите \(-1\).
Перестановкой называется массив, состоящий из \(n\) различных чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, а \([1,2,2]\) — не перестановка (\(2\) встречается дважды), и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве есть \(4\)).
Выходные данные
Для каждого набора входных данных выведите ответ в следующем формате.
Если корректного обмена не существует, выведите \(-1\).
Если корректный ответ существует, выведите \(n\) целых чисел: перестановку \(p\) чисел \(1,2,\ldots,n\), описывающую корректный обмен обувью, где \(i\)-й студент получит обувь \(p_i\)-го студента. Если существуют несколько решений, выведите любое.
Примечание
В первом примере любая перестановка \(p\) чисел \(1,\ldots,n\), где \(p_i\ne i\), описывает корректный обмен, так как у всех одинаковый размер обуви, и все могут носить обувь любого.
Во втором примере можно показать, что нет корректного обмена обувью.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5
1 1 1 1 1
6
3 6 8 13 15 21
|
5 1 2 3 4
-1
|