시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 41 11 11 31.429%

문제

상근이는 박스 N개를 로봇을 이용해서 정렬하려고 한다. 박스에는 1부터 N까지 숫자가 겹치지 않게 써있고, 이 수가 오름차순을 이루도록 박스를 정렬하려고 한다.

상근이가 가지고 있는 로봇에 수열을 입력하면, 위치에 해당하는 박스를 교환하게 된다. 수열에는 같은 위치가 두 번 이상 주어지면 안된다.

예를 들어, 박스가 지금 [4, 1, 5, 2, 3] 순서로 놓여져 있고, 로봇에 [2, 1, 3] 명령을 내렸다고 해보자. 그럼 두 번째 위치에 있는 박스를 위치 1로 옮기고, 첫 번째 박스는 위치 3으로, 세 번째 박스는 위치 2로 이동하게 된다. 박스의 순서는 [1, 5, 4, 2, 3]이 된다.

명령을 가장 적게 이용해서 박스를 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 박스의 수 N이 주어진다. (2 ≤ N ≤ 1000)

다음 줄에는 박스에 붙어있는 숫자가 순서대로 주어진다. 같은 숫자가 두 번 이상 주어지지 않는다.

출력

첫째 줄에 정렬하는데 사용한 명령의 수 X를 출력한다.

그 다음 X개 줄에는 로봇에게 내린 명령을 순서대로 출력한다. 가장 첫 숫자는 수열의 길이이며, 그 다음에 콜론(:)과 공백을 출력하고, 수열의 각 원소를 출력한다.

예제 입력 1

3
3 2 1

예제 출력 1

1
2: 3 1
W3sicHJvYmxlbV9pZCI6IjI4MzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMTVcdWMyYTQgXHVjODE1XHViODJjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViYzE1XHVjMmE0IE5cdWFjMWNcdWI5N2MgXHViODVjXHViZDA3XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWM4MTVcdWI4MmNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJjMTVcdWMyYTRcdWM1ZDBcdWIyOTQgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWFjYjlcdWNlNThcdWM5YzAgXHVjNTRhXHVhYzhjIFx1YzM2OFx1Yzc4OFx1YWNlMCwgXHVjNzc0IFx1YzIxOFx1YWMwMCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3NDQgXHVjNzc0XHViOGU4XHViM2M0XHViODVkIFx1YmMxNVx1YzJhNFx1Yjk3YyBcdWM4MTVcdWI4MmNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWI4NWNcdWJkMDdcdWM1ZDAgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1Yzc4NVx1YjgyNVx1ZDU1OFx1YmE3NCwgXHVjNzA0XHVjZTU4XHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWJjMTVcdWMyYTRcdWI5N2MgXHVhZDUwXHVkNjU4XHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjMjE4XHVjNWY0XHVjNWQwXHViMjk0IFx1YWMxOVx1Yzc0MCBcdWM3MDRcdWNlNThcdWFjMDAgXHViNDUwIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTc0IFx1YzU0OFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHViYzE1XHVjMmE0XHVhYzAwIFx1YzljMFx1YWUwOCBbNCwgMSwgNSwgMiwgM10gXHVjMjFjXHVjMTFjXHViODVjIFx1YjE5M1x1YzVlY1x1YzgzOCBcdWM3ODhcdWFjZTAsIFx1Yjg1Y1x1YmQwN1x1YzVkMCBbMiwgMSwgM10gXHViYTg1XHViODM5XHVjNzQ0IFx1YjBiNFx1YjgzOFx1YjJlNFx1YWNlMCBcdWQ1NzRcdWJjZjRcdWM3OTAuIFx1YWRmOFx1YjdmYyBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYzE1XHVjMmE0XHViOTdjIFx1YzcwNFx1Y2U1OCAxXHViODVjIFx1YzYyZVx1YWUzMFx1YWNlMCwgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWJjMTVcdWMyYTRcdWIyOTQgXHVjNzA0XHVjZTU4IDNcdWM3M2NcdWI4NWMsIFx1YzEzOCBcdWJjODhcdWM5ZjggXHViYzE1XHVjMmE0XHViMjk0IFx1YzcwNFx1Y2U1OCAyXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YmMxNVx1YzJhNFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWIyOTQgWzEsIDUsIDQsIDIsIDNdXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYTg1XHViODM5XHVjNzQ0IFx1YWMwMFx1YzdhNSBcdWM4MDFcdWFjOGMgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YmMxNVx1YzJhNFx1Yjk3YyBcdWM4MTVcdWI4MmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYzE1XHVjMmE0XHVjNzU4IFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMTAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMTVcdWMyYTRcdWM1ZDAgXHViZDk5XHVjNWI0XHVjNzg4XHViMjk0IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMTlcdWM3NDAgXHVjMjJiXHVjNzkwXHVhYzAwIFx1YjQ1MCBcdWJjODggXHVjNzc0XHVjMGMxIFx1YzhmY1x1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTVcdWI4MmNcdWQ1NThcdWIyOTRcdWIzNzAgXHVjMGFjXHVjNmE5XHVkNTVjIFx1YmE4NVx1YjgzOVx1Yzc1OCBcdWMyMTggWFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOCBcdWIyZTRcdWM3NGMgWFx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViODVjXHViZDA3XHVjNWQwXHVhYzhjIFx1YjBiNFx1YjliMCBcdWJhODVcdWI4MzlcdWM3NDQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhYzAwXHVjN2E1IFx1Y2NhYiBcdWMyMmJcdWM3OTBcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yzc3NFx1YmE3MCwgXHVhZGY4IFx1YjJlNFx1Yzc0Y1x1YzVkMCBcdWNmNWNcdWI4NjAoOilcdWFjZmMgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCwgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWMwMSBcdWM2ZDBcdWMxOGNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4MzQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTT1JUIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBvcmRlciB0byBhdXRvbWF0ZSBoaXMgd29ya2xvYWQgYXQgdGhlIGZhY3RvcnksIE1pcmtvIHdhbnRzIHRvIHB1dCB1cCB0byB1c2UgaGlzIG9sZCBib3gtc29ydGluZyByb2JvdC4gVGhlcmUgYXJlIE4gYm94ZXMgaW4gdGhlIGZhY3RvcnksIGFuZCBlYWNoIGJveCBpcyBsYWJlbGxlZCB3aXRoIGFuIHVuaXF1ZSBpbnRlZ2VyIGluIHJhbmdlIDEgdG8gTi4gTWlya28mIzM5O3MgdGFzayBpcyB0byBzb3J0IHRoZSBib3hlcyBpbiB0aGUgYXNjZW5kaW5nIG9yZGVyIG9mIHRoZWlyIGxhYmVscy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+U29ydGluZyByb2JvdCBjYW4gb25seSBwZXJmb3JtIG9uZSBzcGVjaWZpYyBvcGVyYXRpb246IGdpdmVuIHRoZSBzZXF1ZW5jZSBvZiBwb3NpdGlvbnMsIHJvYm90IGNhbiBkbyBhIGN5Y2xpYyBzd2FwIG9mIGJveGVzIGF0IHRob3NlIHBvc2l0aW9ucy4gR2l2ZW4gc2VxdWVuY2UgZG9lcyBub3QgY29udGFpbiBhbnkgcG9zaXRpb24gbW9yZSB0aGFuIG9uY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBsZXQmIzM5O3MgYXNzdW1lIHRoYXQgdGhlIGJveGVzIGFyZSBjdXJyZW50bHkgaW4gb3JkZXIgWzQsIDEsIDUsIDIsIDNdLCBhbmQgTWlya28gcHJvdmlkZXMgaGlzIHJvYm90IHdpdGggdGhlIHNlcXVlbmNlIFsyLCAxLCAzXS4gUm9ib3Qgd2lsbCB0aGVuIHJlYXJyYW5nZSB0aGUgYm94ZXMgc28gdGhhdCB0aGUgc2Vjb25kIGJveCB3aWxsIGdvIHRvIHBvc2l0aW9uIDEsIGZpcnN0IGJveCB3aWxsIGdvIHRvIHRoZSBwb3NpdGlvbiAzLCBhbmQgdGhlIHRoaXJkIG9uZSB3aWxsIHRha2UgdGhlIHBvc2l0aW9uIDIuIE9idGFpbmVkIHNlcXVlbmNlIG9mIGxhYmVscyBpcyBbMSwgNSwgNCwgMiwgM10uJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgc29ydCB0aGUgYm94ZXMgdXNpbmcgdGhlIG1pbmltYWwgbnVtYmVyIG9mIG9wZXJhdGlvbnMuIEVhY2ggc2VxdWVuY2UgZ2l2ZW4gdG8gdGhlIHJvYm90IGNhbiBiZSBhcmJpdHJhcnkgbG9uZy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGludGVnZXIgTiAoMiAmbGU7IE4gJmxlOyAxMDAwKSwgdGhlIG51bWJlciBvZiBib3hlcyBpbiB0aGUgZmFjdG9yeS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBsaW5lIGNvbnRhaW5zIE4gaW50ZWdlcnMgaW4gcmFuZ2UgMSB0byBOLCBsYWJlbHMgb2YgYm94ZXMgaW4gb3JkZXIuIE5vIGludGVnZXIgYXBwZWFycyB0d2ljZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBzaG91bGQgY29udGFpbiB0aGUgaW50ZWdlciBYLCBtaW5pbXVtIG51bWJlciBvZiBvcGVyYXRpb25zIHJlcXVpcmVkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIFggbGluZXMgc2hvdWxkIGNvbnRhaW4gdGhlIHNlcXVlbmNlcyBnaXZlbiB0byByb2JvdCwgb25lIHNlcXVlbmNlIHBlciBsaW5lLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIGxpbmUgc2hvdWxkIHN0YXJ0IHdpdGggdGhlIGxlbmd0aCBvZiB0aGUgc2VxdWVuY2UsIGZvbGxvd2VkIGJ5IGEgY29sb24sIGEgc2luZ2xlIHdoaXRlIHNwYWNlLCBhbmQgdGhlbiBzcGFjZSBzZXBlcmF0ZWQgc2VxdWVuY2Ugb2YgcG9zaXRpb25zLiZuYnNwOzxcL3A+XHJcblxyXG48cD5OT1RFOiBUaGVyZSBtYXkgYmUgbXVsdGlwbGUgc29sdXRpb25zIGFuZCB5b3UgY2FuIG91dHB1dCBhbnkgb2YgdGhlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==