시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 341 156 127 55.947%

문제

힙은 자료의 추가, 우선순위가 제일 높은 자료의 삭제가 가능한 자료구조이다. 이와 같은 힙에는 두 종류가 있는데, 각각 최소-힙, 최대-힙이다. 이 문제에서는 최대-힙을 다루기로 하자.

이와 같은 최대-힙을 이용하면 O(n log n)정렬인 힙 정렬을 할 수 있다. 우리가 다루기로 한 최대-힙을 이용하면 오름차순 정렬을 할 수 있다. 힙 정렬은 크게 두 개의 단계로 나뉘는데, 첫 번째 단계는 주어진 자료들로 힙을 구성하는 단계이고, 두 번째 단계는 이렇게 구성된 힙에서 최댓값을 계속 제거하는 단계이다.

예를 들어 (5, 4, 2, 1, 3)과 같은 힙을 살펴보자. 이 힙에서 최댓값을 삭제하면 (3, 4, 2, 1)이 되고, 힙의 조건을 맞추기 위해 Swap을 한 번 하면 (4, 3, 2, 1)의 힙을 얻는다. 이 힙에서 최댓값을 삭제하면 (1, 3, 2)이 되고, 힙의 조건을 맞추기 위해 Swap을 한 번 하면 (3, 1, 2)가 된다. 다음 단계에서는 (2, 1), (1)이 되고 힙 정렬이 종료된다. 즉, 힙이 (5, 4, 2, 1, 3)과 같이 구성되어 있었다면, 정렬을 위해 Swap을 두 번 사용하게 된다. 하지만 (5, 4, 3, 2, 1)과 같은 힙은 총 네 번의 Swap을 해야 한다.

n이 주어졌을 때, 1부터 n까지의 수를 한 번씩 사용하여 만들 수 있는 힙들 중에서, 위와 같은 Swap 회수가 최대가 되도록 하는 힙을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. (n<=100,000)

출력

첫째 줄에 n개의 정수로 힙을 출력한다.

예제 입력 1

6

예제 출력 1

6 5 3 2 4 1
W3sicHJvYmxlbV9pZCI6IjIyMjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ3OTkgXHVjODE1XHViODJjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ3OTlcdWM3NDAgXHVjNzkwXHViOGNjXHVjNzU4IFx1Y2Q5NFx1YWMwMCwgXHVjNmIwXHVjMTIwXHVjMjFjXHVjNzA0XHVhYzAwIFx1YzgxY1x1Yzc3YyBcdWIxOTJcdWM3NDAgXHVjNzkwXHViOGNjXHVjNzU4IFx1YzBhZFx1YzgxY1x1YWMwMCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjNzkwXHViOGNjXHVhZDZjXHVjODcwXHVjNzc0XHViMmU0LiBcdWM3NzRcdWM2NDAgXHVhYzE5XHVjNzQwIFx1ZDc5OVx1YzVkMFx1YjI5NCBcdWI0NTAgXHVjODg1XHViOTU4XHVhYzAwIFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVhYzAxXHVhYzAxIFx1Y2Q1Y1x1YzE4Yy1cdWQ3OTksIFx1Y2Q1Y1x1YjMwMC1cdWQ3OTlcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjZDVjXHViMzAwLVx1ZDc5OVx1Yzc0NCBcdWIyZTRcdWI4ZThcdWFlMzBcdWI4NWMgXHVkNTU4XHVjNzkwLjxcL3A+XHJcbjxwPlx1Yzc3NFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjZDVjXHViMzAwLVx1ZDc5OVx1Yzc0NCBcdWM3NzRcdWM2YTlcdWQ1NThcdWJhNzQgTyhuIGxvZyBuKVx1YzgxNVx1YjgyY1x1Yzc3OCBcdWQ3OTkgXHVjODE1XHViODJjXHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM2YjBcdWI5YWNcdWFjMDAgXHViMmU0XHViOGU4XHVhZTMwXHViODVjIFx1ZDU1YyBcdWNkNWNcdWIzMDAtXHVkNzk5XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YmE3NCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWMgXHVjODE1XHViODJjXHVjNzQ0IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ3OTkgXHVjODE1XHViODJjXHVjNzQwIFx1ZDA2Y1x1YWM4YyBcdWI0NTAgXHVhYzFjXHVjNzU4IFx1YjJlOFx1YWNjNFx1Yjg1YyBcdWIwOThcdWIyNThcdWIyOTRcdWIzNzAsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHViMmU4XHVhY2M0XHViMjk0IFx1YzhmY1x1YzViNFx1YzljNCBcdWM3OTBcdWI4Y2NcdWI0ZTRcdWI4NWMgXHVkNzk5XHVjNzQ0IFx1YWQ2Y1x1YzEzMVx1ZDU1OFx1YjI5NCBcdWIyZThcdWFjYzRcdWM3NzRcdWFjZTAsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHViMmU4XHVhY2M0XHViMjk0IFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWFkNmNcdWMxMzFcdWI0MWMgXHVkNzk5XHVjNWQwXHVjMTFjIFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWFjYzRcdWMxOGQgXHVjODFjXHVhYzcwXHVkNTU4XHViMjk0IFx1YjJlOFx1YWNjNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0ICg1LCA0LCAyLCAxLCAzKVx1YWNmYyBcdWFjMTlcdWM3NDAgXHVkNzk5XHVjNzQ0IFx1YzBiNFx1ZDNiNFx1YmNmNFx1Yzc5MC4gXHVjNzc0IFx1ZDc5OVx1YzVkMFx1YzExYyBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjMGFkXHVjODFjXHVkNTU4XHViYTc0ICgzLCA0LCAyLCAxKVx1Yzc3NCBcdWI0MThcdWFjZTAsIFx1ZDc5OVx1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWRlXHVjZDk0XHVhZTMwIFx1YzcwNFx1ZDU3NCBTd2FwXHVjNzQ0IFx1ZDU1YyBcdWJjODggXHVkNTU4XHViYTc0ICg0LCAzLCAyLCAxKVx1Yzc1OCBcdWQ3OTlcdWM3NDQgXHVjNWJiXHViMjk0XHViMmU0LiBcdWM3NzQgXHVkNzk5XHVjNWQwXHVjMTFjIFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWMwYWRcdWM4MWNcdWQ1NThcdWJhNzQgKDEsIDMsIDIpXHVjNzc0IFx1YjQxOFx1YWNlMCwgXHVkNzk5XHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5ZGVcdWNkOTRcdWFlMzAgXHVjNzA0XHVkNTc0IFN3YXBcdWM3NDQgXHVkNTVjIFx1YmM4OCBcdWQ1NThcdWJhNzQgKDMsIDEsIDIpXHVhYzAwIFx1YjQxY1x1YjJlNC4gXHViMmU0XHVjNzRjIFx1YjJlOFx1YWNjNFx1YzVkMFx1YzExY1x1YjI5NCAoMiwgMSksICgxKVx1Yzc3NCBcdWI0MThcdWFjZTAgXHVkNzk5IFx1YzgxNVx1YjgyY1x1Yzc3NCBcdWM4ODVcdWI4Y2NcdWI0MWNcdWIyZTQuIFx1Yzk4OSwgXHVkNzk5XHVjNzc0ICg1LCA0LCAyLCAxLCAzKVx1YWNmYyBcdWFjMTlcdWM3NzQgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0IFx1Yzc4OFx1YzVjOFx1YjJlNFx1YmE3NCwgXHVjODE1XHViODJjXHVjNzQ0IFx1YzcwNFx1ZDU3NCBTd2FwXHVjNzQ0IFx1YjQ1MCBcdWJjODggXHVjMGFjXHVjNmE5XHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjICg1LCA0LCAzLCAyLCAxKVx1YWNmYyBcdWFjMTlcdWM3NDAgXHVkNzk5XHVjNzQwIFx1Y2QxZCBcdWIxMjQgXHViYzg4XHVjNzU4IFN3YXBcdWM3NDQgXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG48cD5uXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIDFcdWJkODBcdWQxMzAgblx1YWU0Y1x1YzljMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVkNTVjIFx1YmM4OFx1YzUyOSBcdWMwYWNcdWM2YTlcdWQ1NThcdWM1ZWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkNzk5XHViNGU0IFx1YzkxMVx1YzVkMFx1YzExYywgXHVjNzA0XHVjNjQwIFx1YWMxOVx1Yzc0MCBTd2FwIFx1ZDY4Y1x1YzIxOFx1YWMwMCBcdWNkNWNcdWIzMDBcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1ZDU1OFx1YjI5NCBcdWQ3OTlcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChuJmx0Oz0xMDAsMDAwKTxcL3A+Iiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBuXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWQ3OTlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjIyMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhlYXBzb3J0IiwiZGVzY3JpcHRpb24iOiI8cD5BIHdlbGwga25vd24gYWxnb3JpdGhtIGNhbGxlZCBoZWFwc29ydCBpcyBhIGRldGVybWluaXN0aWMgc29ydGluZyBhbGdvcml0aG0gdGFraW5nIE8obiBsb2cgbikgdGltZSBhbmQgTygxKSBhZGRpdGlvbmFsIG1lbW9yeS4gTGV0IHVzIGRlc2NyaWJlIGFzY2VuZGluZyBzb3J0aW5nIG9mIGFuIGFycmF5IG9mIGRpXHVmYjAwZXJlbnQgaW50ZWdlciBudW1iZXJzLjxcL3A+XHJcblxyXG48cD5UaGUgYWxnb3JpdGhtIGNvbnNpc3RzIG9mIHR3byBwaGFzZXMuIEluIHRoZSBmaXJzdCBwaGFzZSwgY2FsbGVkIGhlYXBpZmljYXRpb24sIHRoZSBhcnJheSBvZiBpbnRlZ2VycyB0byBiZSBzb3J0ZWQgaXMgY29udmVydGVkIHRvIGEgaGVhcC4gQW4gYXJyYXkgYVsxIC4uLiBuXSBvZiBpbnRlZ2VycyBpcyBjYWxsZWQgYSBoZWFwIGlmIGZvciBhbGwgMSAmbGU7IGkgJmxlOyBuIHRoZSBmb2xsb3dpbmcgaGVhcCBjb25kaXRpb25zIGFyZSBzYXRpc2ZpZWQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+aWYgMmkgJmxlOyBuIHRoZW4gYVtpXSAmZ3Q7IGFbMmldOzxcL2xpPlxyXG5cdDxsaT5pZiAyaSArIDEgJmxlOyBuIHRoZW4gYVtpXSAmZ3Q7IGFbMmkgKyAxXS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5XZSBjYW4gaW50ZXJwcmV0IGFuIGFycmF5IGFzIGEgYmluYXJ5IHRyZWUsIGNvbnNpZGVyaW5nIGNoaWxkcmVuIG9mIGVsZW1lbnQgYVtpXSB0byBiZSBhWzJpXSBhbmQgYVsyaSArIDFdLiBJbiB0aGlzIGNhc2UgdGhlIHBhcmVudCBvZiBhW2ldIGlzIGFbaSBkaXYgMl0sIHdoZXJlIGkgZGl2IDIgPSBiaVwvMmMuIEluIHRlcm1zIG9mIHRyZWVzIHRoZSBwcm9wZXJ0eSBvZiBiZWluZyBhIGhlYXAgbWVhbnMgdGhhdCBmb3IgZWFjaCBub2RlIGl0cyB2YWx1ZSBpcyBncmVhdGVyIHRoYW4gdGhlIHZhbHVlcyBvZiBpdHMgY2hpbGRyZW4uPFwvcD5cclxuXHJcbjxwPkluIHRoZSBzZWNvbmQgcGhhc2UgdGhlIGhlYXAgaXMgdHVybmVkIGludG8gYSBzb3J0ZWQgYXJyYXkuIEJlY2F1c2Ugb2YgdGhlIGhlYXAgY29uZGl0aW9uIHRoZSBncmVhdGVzdCBlbGVtZW50IGluIHRoZSBoZWFwaWZpZWQgYXJyYXkgaXMgYVsxXS4gTGV0IHVzIGV4Y2hhbmdlIGl0IHdpdGggYVtuXSwgbm93IHRoZSBncmVhdGVzdCBlbGVtZW50IG9mIHRoZSBhcnJheSBpcyBhdCBpdHMgY29ycmVjdCBwb3NpdGlvbiBpbiB0aGUgc29ydGVkIGFycmF5LiBUaGlzIGlzIGNhbGxlZCBleHRyYWN0LW1heC48XC9wPlxyXG5cclxuPHA+Tm93IGxldCB1cyBjb25zaWRlciB0aGUgcGFydCBvZiB0aGUgYXJyYXkgYVsxIC4uLiBuICZtaW51czsgMV0uIEl0IG1heSBiZSBub3QgYSBoZWFwIGJlY2F1c2UgdGhlIGhlYXAgY29uZGl0aW9uIG1heSBmYWlsIGZvciBpID0gMS4gSWYgaXQgaXMgc28gKHRoYXQgaXMsIGVpdGhlciBhWzJdIG9yIGFbM10sIG9yIGJvdGggYXJlIGdyZWF0ZXIgdGhhbiBhWzFdKSBsZXQgdXMgZXhjaGFuZ2UgdGhlIGdyZWF0ZXN0IGNoaWxkIG9mIGFbMV0gd2l0aCBpdCwgcmVzdG9yaW5nIHRoZSBoZWFwIGNvbmRpdGlvbiBmb3IgaSA9IDEuIE5vdyBpdCBpcyBwb3NzaWJsZSB0aGF0IHRoZSBoZWFwIGNvbmRpdGlvbiBmYWlscyBmb3IgdGhlIHBvc2l0aW9uIHRoYXQgbm93IGNvbnRhaW5zIHRoZSBmb3JtZXIgdmFsdWUgb2YgYVsxXS4gQXBwbHkgdGhlIHNhbWUgcHJvY2VkdXJlIHRvIGl0LCBleGNoYW5naW5nIGl0IHdpdGggaXRzIGdyZWF0ZXN0IGNoaWxkLiBQcm9jZWVkaW5nIHNvIHdlIGNvbnZlcnQgdGhlIHdob2xlIGFycmF5IGFbMSAuLi4gbiAmbWludXM7IDFdIHRvIGEgaGVhcC4gVGhpcyBwcm9jZWR1cmUgaXMgY2FsbGVkIHNpZnRpbmcgZG93bi4gQWZ0ZXIgY29udmVydGluZyB0aGUgcGFydCBhWzEgLi4uIG4gJm1pbnVzOyAxXSB0byBhIGhlYXAgYnkgc2lmdGluZywgd2UgYXBwbHkgZXh0cmFjdC1tYXggYWdhaW4sIHB1dHRpbmcgc2Vjb25kIGdyZWF0ZXN0IGVsZW1lbnQgb2YgdGhlIGFycmF5IHRvIGFbbiAmbWludXM7IDFdLCBhbmQgc28gb24uPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBsZXQgdXMgc2VlIGhvdyB0aGUgaGVhcCBhID0gKDUsIDQsIDIsIDEsIDMpIGlzIGNvbnZlcnRlZCB0byBhIHNvcnRlZCBhcnJheS4gTGV0IHVzIG1ha2UgdGhlIGZpcnN0IGV4dHJhY3QtbWF4LiBBZnRlciB0aGF0IHRoZSBhcnJheSB0dXJucyB0byAoMywgNCwgMiwgMSwgNSkuIEhlYXAgY29uZGl0aW9uIGZhaWxzIGZvciBhWzFdID0gMyBiZWNhdXNlIGl0cyBjaGlsZCBhWzJdID0gNCBpcyBncmVhdGVyIHRoYW4gaXQuIExldCB1cyBzaWZ0IGl0IGRvd24sIGV4Y2hhbmdpbmcgYVsxXSBhbmQgYVsyXS4gTm93IHRoZSBhcnJheSBpcyAoNCwgMywgMiwgMSwgNSkuIFRoZSBoZWFwIGNvbmRpdGlvbiBpcyBzYXRpc2ZpZWQgZm9yIGFsbCBlbGVtZW50cywgc28gc2lmdGluZyBpcyBvdmVyLiBMZXQgdXMgbWFrZSBleHRyYWN0LW1heCBhZ2Fpbi4gTm93IHRoZSBhcnJheSB0dXJucyB0byAoMSwgMywgMiwgNCwgNSkuIEFnYWluIHRoZSBoZWFwIGNvbmRpdGlvbiBmYWlscyBmb3IgYVsxXTsgZXhjaGFuZ2luZyBpdCB3aXRoIGl0cyBncmVhdGVzdCBjaGlsZCB3ZSBnZXQgdGhlIGFycmF5ICgzLCAxLCAyLCA0LCA1KSB3aGljaCBpcyB0aGUgY29ycmVjdCBoZWFwLiBTbyB3ZSBtYWtlIGV4dHJhY3QtbWF4IGFuZCBnZXQgKDIsIDEsIDMsIDQsIDUpLiBUaGlzIHRpbWUgdGhlIGhlYXAgY29uZGl0aW9uIGlzIHNhdGlzZmllZCBmb3IgYWxsIGVsZW1lbnRzLCBzbyB3ZSBtYWtlIGV4dHJhY3QtbWF4LCBnZXR0aW5nICgxLCAyLCAzLCA0LCA1KS4gVGhlIGxlYWRpbmcgcGFydCBvZiB0aGUgYXJyYXkgaXMgYSBoZWFwLCBhbmQgdGhlIGxhc3QgZXh0cmFjdC1tYXggZmluYWxseSBnaXZlcyAoMSwgMiwgMywgNCwgNSkuPFwvcD5cclxuXHJcbjxwPkl0IGlzIGtub3duIHRoYXQgaGVhcGlmaWNhdGlvbiBjYW4gYmUgZG9uZSBpbiBPKG4pIHRpbWUuIFRoZXJlZm9yZSwgdGhlIG1vc3QgdGltZSBjb25zdW1pbmcgb3BlcmF0aW9uIGluIGhlYXBzb3J0IGFsZ29yaXRobSBpcyBzaWZ0aW5nLCB3aGljaCB0YWtlcyBPKG4gbG9nIG4pIHRpbWUuPFwvcD5cclxuXHJcbjxwPkluIHRoaXMgcHJvYmxlbSB5b3UgaGF2ZSB0byBmaW5kIGEgaGVhcGlmaWVkIGFycmF5IGNvbnRhaW5pbmcgZGlcdWZiMDBlcmVudCBudW1iZXJzIGZyb20gMSB0byBuLCBzdWNoIHRoYXQgd2hlbiBjb252ZXJ0aW5nIGl0IHRvIGEgc29ydGVkIGFycmF5LCB0aGUgdG90YWwgbnVtYmVyIG9mIGV4Y2hhbmdlcyBpbiBhbGwgc2lmdGluZyBvcGVyYXRpb25zIGlzIG1heGltYWwgcG9zc2libGUuIEluIHRoZSBleGFtcGxlIGFib3ZlIHRoZSBudW1iZXIgb2YgZXhjaGFuZ2VzIGlzIDEgKyAxICsgMCArIDAgKyAwID0gMiwgd2hpY2ggaXMgbm90IHRoZSBtYXhpbXVtLiAoNSwgNCwgMywgMiwgMSkgZ2l2ZXMgdGhlIG1heGltYWwgbnVtYmVyIG9mIDQgZXhjaGFuZ2VzIGZvciBuID0gNS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IGZpbGUgY29udGFpbnMgbiAoMSAmbGU7IG4gJmxlOyA1MCAwMDApLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgYXJyYXkgY29udGFpbmluZyBuIGRpXHVmYjAwZXJlbnQgaW50ZWdlciBudW1iZXJzIGZyb20gMSB0byBuLCBzdWNoIHRoYXQgaXQgaXMgYSBoZWFwLCBhbmQgd2hlbiBjb252ZXJ0aW5nIGl0IHRvIGEgc29ydGVkIGFycmF5LCB0aGUgdG90YWwgbnVtYmVyIG9mIGV4Y2hhbmdlcyBpbiBzaWZ0aW5nIG9wZXJhdGlvbnMgaXMgbWF4aW1hbCBwb3NzaWJsZS4gU2VwYXJhdGUgbnVtYmVycyBieSBzcGFjZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d