Задача H. Лэнгфорд плюс один

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Назовем расширенной последовательностью Лэнгфорда такую последовательность из 2N целых чисел, что:

  1. Все числа находятся в диапазоне то 1 до N + 1.
  2. Каждое число, входящее в последовательность, встречается в ней ровно два раза.
  3. Между двумя вхождениями числа k в последовательность находятся ровно k других чисел.

Требуется по данному N найти соответствующую расширенную последовательность Лэнгфорда.

Формат входного файла

Во входном файле содержится целое число N.

Формат выходного файла

В выходном файле должно содержаться 2N целых чисел — элементы последовательности. Если решений несколько, вывести любое из них.

Ограничения

4 ≤ N ≤ 40

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4
2 3 4 2 1 3 1 4
2
5
4 5 6 2 3 4 2 5 3 6 

0.098s 0.012s 13