В последовательности целых чисел \(a\) длины \(n\) каждый элемент изначально равен \(-1\).
У Мизуки есть две пишущие машинки, первая из которых пишет слева направо с указателем, изначально указывающим на \(1\), а вторая пишет буквы справа налево с указателем, изначально указывающим на \(n\).
Мизуки выбирает одну из пишущих машинок и выполняет с ней следующие операции, пока \(a\) не превратится в перестановку элементов \([1, 2, \ldots, n]\):
- Запись числа: записать минимальное целое положительное число, не встречающееся в \(a\), на позицию \(a_i\). Здесь \(i\) — позиция, на которую указывает указатель. Такая операция может быть выполнена только при \(a_i = -1\).
- Возврат каретки: возврат указателя на начальную позицию (т.е. \(1\) для первой машинки, \(n\) для второй).
- Перемещение указателя: переместить указатель на следующую позицию. Пусть \(i\) — это позиция, на которую указывает указатель до этой операции. Если Мизуки использует первую пишущую машинку, то \(i := i + 1\), а в противном случае \(i := i - 1\). Такая операция может быть выполнена только в том случае, если после ее выполнения выполняется условие \(1 \le i \le n\).
Ваша задача — построить любую перестановку \(p\) длины \(n\), такую, чтобы минимальное количество операций возврата каретки, необходимое для того, чтобы получить \(a = p\), было одинаковым независимо от того, какой машинкой пользуется Мизуки.
Выходные данные
Для каждого набора входных данных выведите строку из \(n\) целых чисел, представляющих перестановку \(p\) длины \(n\), такую, что минимальное количество операций возврата каретки, необходимое для того, чтобы получить \(a = p\), было одинаковым независимо от того, какой пишущей машинкой пользуется Мизуки, или \(-1\), если это невозможно.
Если существует несколько допустимых перестановок, вы можете вывести любую из них.
Примечание
В первом наборе входных данных можно сделать \(a = p = [1]\), используя \(0\) операций возврата каретки.
Для второго набора входных данных найдем необходимое количество возвратов каретки, чтобы получить \(a = p = [1, 2]\).
Если Мизуки использует первую пишущую машинку:
- Запись числа: записать \(1\) в \(a_1\), \(a\) станет \([1, -1]\).
- Перемещение указателя: переместить указатель на следующую позицию. (т.е. \(2\)).
- Запись числа: записать \(2\) в \(a_2\), \(a\) станет \([1, 2]\).
Если Мизуки использует вторую пишущую машинку:
- Перемещение указателя: переместить указатель на следующую позицию. (т.е. \(1\)).
- Запись числа: записать \(1\) в \(a_1\), \(a\) станет \([1, -1]\).
- Возврат каретки: вернуть указатель на \(2\).
- Запись числа: записать \(2\) в \(a_2\), \(a\) станет \([1, 2]\).
Можно доказать, что минимальное количество возвратов каретки, необходимое для преобразования \(a\) в \(p\) при использовании первой пишущей машинки, равно \(0\), а при использовании второй — \(1\), поэтому данная перестановка не удовлетворяет условию.
Аналогично, \(p = [2, 1]\) также не является допустимой, поэтому для \(n = 2\) решения не существует.
В третьем примере можно сделать \(a = p = [3, 1, 2]\), требующую \(1\) возврат каретки с использованием первой или второй пишущей машинки. Можно показать, что нельзя записать \(p\) используя \(0\) возвратов каретки.
С помощью первой пишущей машинки можно записать перестановку так:
- Переместить указатель: переместить указатель на следующую позицию (то есть \(2\))
- Записать число: записать \(1\) в позицию \(a_2\), \(a\) становится \([-1, 1, -1]\)
- Переместить указатель: переместить указатель на следующую позицию (то есть \(3\))
- Записать число: записать \(2\) в позицию \(a_3\), \(a\) становится \([-1, 1, 2]\)
- Возврат каретки: вернуть указатель в позицию \(1\).
- Записать число: записать \(3\) в позицию \(a_1\), \(a\) становится \([3,1,2]\)
Используя вторую машинку, можно сделать так:
- Переместить указатель: переместить указатель на следующую позицию (то есть \(2\))
- Записать число: записать \(1\) в позицию \(a_2\), \(a\) становится \([-1, 1, -1]\)
- Возврат каретки: вернуть указатель в позицию \(3\).
- Записать число: записать \(2\) to \(a_3\), \(a\) становится \([-1, 1, 2]\)
- Переместить указатель: переместить указатель на следующую позицию (то есть \(2\))
- Переместить указатель: переместить указатель на следующую позицию (то есть \(1\))
- Записать число: записать \(3\) to \(a_1\), \(a\) становится \([3, 1, 2]\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1
2
3
|
1
-1
3 1 2
|