시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB156185470162.256%

문제

1부터 N까지의 숫자가 적힌 카드가 있다. 찬유는 이 카드를 가지고 마술을 하려 한다. 마술을 하는 순서는 다음과 같다.

  1. 먼저 1부터 N까지의 숫자가 적힌 카드에서 첫 번째 카드를 가장 뒤로 옮긴다. 그러고 나서 첫 번째 카드를 책상 위에 올려놓는다. 그런데 그 카드는 1이 되어야 한다.
  2. 그리고 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고, 또 가장 앞에 있는 카드를 가장 뒤로 옮긴다.(2번 반복) 그리고 가장 앞에 있는 카드를 책상 위에 올려놓는다. 그런데 그 카드는 2가 되어야 한다.
  3. 또 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고... (3번 반복) 그리고 가장 앞에 있는 카드를 책상위에 올려놓는데 그것은 3이 된다.
  4. 또 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고.. (4번 반복) 그리고 가장 앞에 있는 카드를 책상 위에 올려놓는데 그것은 4이다.
  5. 위 과정을 계속 반복하여 N번 카드만 남을 때 까지 반복한다.

위와 같은 카드를 하려면 미리 카드의 순서를 알고 있어야 한다. 카드의 개수 N이 주어져 있을 때 위의 마술을 하기 위한 카드의 초기 순서를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 카드의 개수 N(1 ≤ N ≤ 1,000)이 주어진다.

출력

첫 번째 줄부터 N번째 줄까지 차례로 카드의 순서를 출력한다.

예제 입력 1

4

예제 출력 1

2 1 4 3

힌트

  1. 2 1 4 3에서 2를 가장 뒤로 옮긴다. (1 4 3 2)
  2. 1을 책상 위에 옮겨놓는다. (4 3 2)
  3. 4 3 2 에서 4, 3을 뒤로 옮긴다. (2 4 3)
  4. 2를 책상 위로 옮겨놓는다. (4 3)
  5. 4 3 에서 가장 앞에 있는 것을 뒤로 3번 옮긴    다. (3 4)
  6. 3을 책상 위로 옮겨놓는다. (4)
  7. 4를 책상 위로 옮겨놓는다. (완료)
W3sicHJvYmxlbV9pZCI6IjE4MzUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlNzRcdWI0ZGMiLCJkZXNjcmlwdGlvbiI6IjxwPjFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjODAxXHVkNzhjIFx1Y2U3NFx1YjRkY1x1YWMwMCBcdWM3ODhcdWIyZTQuIFx1Y2MyY1x1YzcyMFx1YjI5NCBcdWM3NzQgXHVjZTc0XHViNGRjXHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWI5YzhcdWMyMjBcdWM3NDQgXHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC4gXHViOWM4XHVjMjIwXHVjNzQ0IFx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWJhM2NcdWM4MDAgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwXHVjNzU4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWM4MDFcdWQ3OGMgXHVjZTc0XHViNGRjXHVjNWQwXHVjMTFjIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjZTc0XHViNGRjXHViOTdjIFx1YWMwMFx1YzdhNSBcdWI0YTRcdWI4NWMgXHVjNjJlXHVhZTM0XHViMmU0LiBcdWFkZjhcdWI3ZWNcdWFjZTAgXHViMDk4XHVjMTFjIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjZTc0XHViNGRjXHViOTdjIFx1Y2M0NVx1YzBjMSBcdWM3MDRcdWM1ZDAgXHVjNjJjXHViODI0XHViMTkzXHViMjk0XHViMmU0LiBcdWFkZjhcdWI3ZjBcdWIzNzAgXHVhZGY4IFx1Y2U3NFx1YjRkY1x1YjI5NCAxXHVjNzc0IFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWRmOFx1YjlhY1x1YWNlMCBcdWIwYThcdWM3NDAgXHVjZTc0XHViNGRjIFx1YzkxMVx1YzVkMFx1YzExYyBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Y2U3NFx1YjRkY1x1Yjk3YyBcdWFjMDBcdWM3YTUgXHViNGE0XHViODVjIFx1YzYyZVx1YWUzMFx1YWNlMCwgXHViNjEwIFx1YWMwMFx1YzdhNSBcdWM1NWVcdWM1ZDAgXHVjNzg4XHViMjk0IFx1Y2U3NFx1YjRkY1x1Yjk3YyBcdWFjMDBcdWM3YTUgXHViNGE0XHViODVjIFx1YzYyZVx1YWUzNFx1YjJlNC4oMlx1YmM4OCBcdWJjMThcdWJjZjUpIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFjMDBcdWM3YTUgXHVjNTVlXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWNlNzRcdWI0ZGNcdWI5N2MgXHVjYzQ1XHVjMGMxIFx1YzcwNFx1YzVkMCBcdWM2MmNcdWI4MjRcdWIxOTNcdWIyOTRcdWIyZTQuIFx1YWRmOFx1YjdmMFx1YjM3MCBcdWFkZjggXHVjZTc0XHViNGRjXHViMjk0IDJcdWFjMDAgXHViNDE4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViNjEwIFx1YjBhOFx1Yzc0MCBcdWNlNzRcdWI0ZGMgXHVjOTExXHVjNWQwXHVjMTFjIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjZTc0XHViNGRjXHViOTdjIFx1YWMwMFx1YzdhNSBcdWI0YTRcdWI4NWMgXHVjNjJlXHVhZTMwXHVhY2UwLi4uICgzXHViYzg4IFx1YmMxOFx1YmNmNSkgXHVhZGY4XHViOWFjXHVhY2UwIFx1YWMwMFx1YzdhNSBcdWM1NWVcdWM1ZDAgXHVjNzg4XHViMjk0IFx1Y2U3NFx1YjRkY1x1Yjk3YyBcdWNjNDVcdWMwYzFcdWM3MDRcdWM1ZDAgXHVjNjJjXHViODI0XHViMTkzXHViMjk0XHViMzcwIFx1YWRmOFx1YWM4M1x1Yzc0MCAzXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViNjEwIFx1YjBhOFx1Yzc0MCBcdWNlNzRcdWI0ZGMgXHVjOTExXHVjNWQwXHVjMTFjIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjZTc0XHViNGRjXHViOTdjIFx1YWMwMFx1YzdhNSBcdWI0YTRcdWI4NWMgXHVjNjJlXHVhZTMwXHVhY2UwLi4gKDRcdWJjODggXHViYzE4XHViY2Y1KSBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhYzAwXHVjN2E1IFx1YzU1ZVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjZTc0XHViNGRjXHViOTdjIFx1Y2M0NVx1YzBjMSBcdWM3MDRcdWM1ZDAgXHVjNjJjXHViODI0XHViMTkzXHViMjk0XHViMzcwIFx1YWRmOFx1YWM4M1x1Yzc0MCA0XHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM3MDQgXHVhY2ZjXHVjODE1XHVjNzQ0IFx1YWNjNFx1YzE4ZCBcdWJjMThcdWJjZjVcdWQ1NThcdWM1ZWMgTlx1YmM4OCBcdWNlNzRcdWI0ZGNcdWI5Y2MgXHViMGE4XHVjNzQ0IFx1YjU0YyBcdWFlNGNcdWM5YzAgXHViYzE4XHViY2Y1XHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjZTc0XHViNGRjXHViOTdjIFx1ZDU1OFx1YjgyNFx1YmE3NCBcdWJiZjhcdWI5YWMgXHVjZTc0XHViNGRjXHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWM1NGNcdWFjZTAgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjZTc0XHViNGRjXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzgzOCBcdWM3ODhcdWM3NDQgXHViNTRjIFx1YzcwNFx1Yzc1OCBcdWI5YzhcdWMyMjBcdWM3NDQgXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWNlNzRcdWI0ZGNcdWM3NTggXHVjZDA4XHVhZTMwIFx1YzIxY1x1YzExY1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2U3NFx1YjRkY1x1Yzc1OCBcdWFjMWNcdWMyMTggTigxICZsZTsgTiAmbGU7IDEsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YmM4OFx1YzlmOCBcdWM5MDRcdWFlNGNcdWM5YzAgXHVjYzI4XHViODQwXHViODVjIFx1Y2U3NFx1YjRkY1x1Yzc1OCBcdWMyMWNcdWMxMWNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8b2w+XHJcblx0PGxpPjIgMSA0IDNcdWM1ZDBcdWMxMWMgMlx1Yjk3YyBcdWFjMDBcdWM3YTUgXHViNGE0XHViODVjIFx1YzYyZVx1YWUzNFx1YjJlNC4gKDEgNCAzIDIpPFwvbGk+XHJcblx0PGxpPjFcdWM3NDQgXHVjYzQ1XHVjMGMxIFx1YzcwNFx1YzVkMCBcdWM2MmVcdWFjYThcdWIxOTNcdWIyOTRcdWIyZTQuICg0IDMgMik8XC9saT5cclxuXHQ8bGk+NCAzIDIgXHVjNWQwXHVjMTFjIDQsIDNcdWM3NDQgXHViNGE0XHViODVjIFx1YzYyZVx1YWUzNFx1YjJlNC4gKDIgNCAzKTxcL2xpPlxyXG5cdDxsaT4yXHViOTdjIFx1Y2M0NVx1YzBjMSBcdWM3MDRcdWI4NWMgXHVjNjJlXHVhY2E4XHViMTkzXHViMjk0XHViMmU0LiAoNCAzKTxcL2xpPlxyXG5cdDxsaT40IDMgXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWM1NWVcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWI0YTRcdWI4NWMgM1x1YmM4OCBcdWM2MmVcdWFlMzQmbmJzcDsmbmJzcDsmbmJzcDsgXHViMmU0LiAoMyA0KTxcL2xpPlxyXG5cdDxsaT4zXHVjNzQ0IFx1Y2M0NVx1YzBjMSBcdWM3MDRcdWI4NWMgXHVjNjJlXHVhY2E4XHViMTkzXHViMjk0XHViMmU0LiAoNCk8XC9saT5cclxuXHQ8bGk+NFx1Yjk3YyBcdWNjNDVcdWMwYzEgXHVjNzA0XHViODVjIFx1YzYyZVx1YWNhOFx1YjE5M1x1YjI5NFx1YjJlNC4gKFx1YzY0NFx1YjhjYyk8XC9saT5cclxuPFwvb2w+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTgzNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNhcmQgVHJpY2siLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBtYWdpY2lhbiBzaHVmXHVmYjAyZXMgYSBzbWFsbCBwYWNrIG9mIGNhcmRzLCBob2xkcyBpdCBmYWNlIGRvd24gYW5kIHBlcmZvcm1zIHRoZSBmb2xsb3dpbmcgcHJvY2VkdXJlOjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlRoZSB0b3AgY2FyZCBpcyBtb3ZlZCB0byB0aGUgYm90dG9tIG9mIHRoZSBwYWNrLiBUaGUgbmV3IHRvcCBjYXJkIGlzIGRlYWx0IGZhY2UgdXAgb250byB0aGUgdGFibGUuIEl0IGlzIHRoZSBBY2Ugb2YgU3BhZGVzLjxcL2xpPlxyXG5cdDxsaT5Ud28gY2FyZHMgYXJlIG1vdmVkIG9uZSBhdCBhIHRpbWUgZnJvbSB0aGUgdG9wIHRvIHRoZSBib3R0b20uIFRoZSBuZXh0IGNhcmQgaXMgZGVhbHQgZmFjZSB1cCBvbnRvIHRoZSB0YWJsZS4gSXQgaXMgdGhlIFR3byBvZiBTcGFkZXMuPFwvbGk+XHJcblx0PGxpPlRocmVlIGNhcmRzIGFyZSBtb3ZlZCBvbmUgYXQgYSB0aW1lIC4gLiAuPFwvbGk+XHJcblx0PGxpPlRoaXMgZ29lcyBvbiB1bnRpbCB0aGUgbnRoIGFuZCBsYXN0IGNhcmQgdHVybnMgb3V0IHRvIGJlIHRoZSBuIG9mIFNwYWRlcy48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5UaGlzIGltcHJlc3NpdmUgdHJpY2sgd29ya3MgaWYgdGhlIG1hZ2ljaWFuIGtub3dzIGhvdyB0byBhcnJhbmdlIHRoZSBjYXJkcyBiZWZvcmVoYW5kIChhbmQga25vd3MgaG93IHRvIGdpdmUgYSBmYWxzZSBzaHVmXHVmYjAyZSkuIFlvdXIgcHJvZ3JhbSBoYXMgdG8gZGV0ZXJtaW5lIHRoZSBpbml0aWFsIG9yZGVyIG9mIHRoZSBjYXJkcyBmb3IgYSBnaXZlbiBudW1iZXIgb2YgY2FyZHMsIDEgJmxlOyBuICZsZTsgMSwwMDAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgXHVmYjAxcnN0IGxpbmUgb2YgdGhlIGlucHV0IGlzIGEgc2luZ2xlIHBvc2l0aXZlIGludGVnZXIsIHRlbGxpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIHRvIGZvbGxvdy4gRWFjaCBjYXNlIGNvbnNpc3RzIG9mIG9uZSBsaW5lIGNvbnRhaW5pbmcgdGhlIGludGVnZXIgbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBhIGxpbmUgd2l0aCB0aGUgY29ycmVjdCBwZXJtdXRhdGlvbiBvZiB0aGUgdmFsdWVzIDEgdG8gbiwgc3BhY2Ugc2VwYXJhdGVkLiBUaGUgXHVmYjAxcnN0IG51bWJlciBzaG93aW5nIHRoZSB0b3AgY2FyZCBvZiB0aGUgcGFjaywgZXRjIC4gLiAuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==