시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 13 4 4 44.444%

문제

상근이는 몇 달전에 대박의 꿈을 안고 아이폰 앱의 세계에 발을 들였다. 상근이는 게임을 하나 만들었는데, 이 게임에는 전체 사용자의 순위를 보여주는 기능이 있다. 상근이는 점수를 내림차순으로 정렬해 사용자의 순위를 보여주려고 한다.

사용자의 점수를 저장하는데 사용한 자료구조는 오직 연산 하나만 수행할 수 있다. 이 연산은 i번째 사용자를 j번째로 옮기는데, 다른 사용자의 상대적인 순서를 바꾸지 않는다.

예를 들어, i>j인 경우에 j와 i-1번 사이의 사용자의 순위는 1씩 증가한다. 반대로 i<j인 경우에는 i+1과 j 사이의 사용자의 순위가 1씩 감소한다.

연산을 한 번 사용할 때, 이동시킬 사용자를 찾는데 i단계, 이동할 위치를 찾는데 j단계가 필요하기 때문에, i번째 사용자를 j번째로 옮기는데 드는 비용은 i+j이다. 순위는 1부터 시작한다.

현재 자료구조에 저장된 점수가 주어졌을 때, 사용자를 내림차순으로 정렬하기 위해 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 저장된 점수의 수 n (2 ≤ n ≤ 1000) 이 주어진다. 다음 줄에는 점수 si가 현재 자료구조에 저장되어 있는 순서대로 주어진다. (0 ≤ si ≤ 1,000,000) 두 점수가 같은 경우는 없다.

출력

첫째 줄에 점수를 내림차순으로 정렬하기 위해 필요한 이동 횟수를 출력한다. 다음 줄에는 각 이동을 순서대로 출력한다. i번째 점수를 j번째로 옮긴 경우에는 i j를 출력한다.

예제 입력 1

5
20
30
5
15
10

예제 출력 1

2
2 1
3 5
W3sicHJvYmxlbV9pZCI6IjI0MzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMWNcdWM3MDQgXHVjODE1XHViODJjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViYTg3IFx1YjJlY1x1YzgwNFx1YzVkMCBcdWIzMDBcdWJjMTVcdWM3NTggXHVhZmM4XHVjNzQ0IFx1YzU0OFx1YWNlMCBcdWM1NDRcdWM3NzRcdWQzZjAgXHVjNTcxXHVjNzU4IFx1YzEzOFx1YWNjNFx1YzVkMCBcdWJjMWNcdWM3NDQgXHViNGU0XHVjNjAwXHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyOTRcdWIzNzAsIFx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM1ZDBcdWIyOTQgXHVjODA0XHVjY2I0IFx1YzBhY1x1YzZhOVx1Yzc5MFx1Yzc1OCBcdWMyMWNcdWM3MDRcdWI5N2MgXHViY2Y0XHVjNWVjXHVjOGZjXHViMjk0IFx1YWUzMFx1YjJhNVx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM4MTBcdWMyMThcdWI5N2MgXHViMGI0XHViOWJjXHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1YzgxNVx1YjgyY1x1ZDU3NCBcdWMwYWNcdWM2YTlcdWM3OTBcdWM3NTggXHVjMjFjXHVjNzA0XHViOTdjIFx1YmNmNFx1YzVlY1x1YzhmY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBhY1x1YzZhOVx1Yzc5MFx1Yzc1OCBcdWM4MTBcdWMyMThcdWI5N2MgXHVjODAwXHVjN2E1XHVkNTU4XHViMjk0XHViMzcwIFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWM3OTBcdWI4Y2NcdWFkNmNcdWM4NzBcdWIyOTQgXHVjNjI0XHVjOWMxIFx1YzVmMFx1YzBiMCBcdWQ1NThcdWIwOThcdWI5Y2MgXHVjMjE4XHVkNTg5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWM1ZjBcdWMwYjBcdWM3NDAgaVx1YmM4OFx1YzlmOCBcdWMwYWNcdWM2YTlcdWM3OTBcdWI5N2Mgalx1YmM4OFx1YzlmOFx1Yjg1YyBcdWM2MmVcdWFlMzBcdWIyOTRcdWIzNzAsIFx1YjJlNFx1Yjk3OCBcdWMwYWNcdWM2YTlcdWM3OTBcdWM3NTggXHVjMGMxXHViMzAwXHVjODAxXHVjNzc4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWJjMTRcdWFmYjhcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBpJmd0O2pcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwIGpcdWM2NDAgaS0xXHViYzg4IFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWMwYWNcdWM2YTlcdWM3OTBcdWM3NTggXHVjMjFjXHVjNzA0XHViMjk0IDFcdWM1MjkgXHVjOTlkXHVhYzAwXHVkNTVjXHViMmU0LiBcdWJjMThcdWIzMDBcdWI4NWMgaSZsdDtqXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBpKzFcdWFjZmMgaiBcdWMwYWNcdWM3NzRcdWM3NTggXHVjMGFjXHVjNmE5XHVjNzkwXHVjNzU4IFx1YzIxY1x1YzcwNFx1YWMwMCAxXHVjNTI5IFx1YWMxMFx1YzE4Y1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWYwXHVjMGIwXHVjNzQ0IFx1ZDU1YyBcdWJjODggXHVjMGFjXHVjNmE5XHVkNTYwIFx1YjU0YywgXHVjNzc0XHViM2Q5XHVjMmRjXHVkMGFjIFx1YzBhY1x1YzZhOVx1Yzc5MFx1Yjk3YyBcdWNjM2VcdWIyOTRcdWIzNzAgaVx1YjJlOFx1YWNjNCwgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWNjM2VcdWIyOTRcdWIzNzAgalx1YjJlOFx1YWNjNFx1YWMwMCBcdWQ1NDRcdWM2OTRcdWQ1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBpXHViYzg4XHVjOWY4IFx1YzBhY1x1YzZhOVx1Yzc5MFx1Yjk3YyBqXHViYzg4XHVjOWY4XHViODVjIFx1YzYyZVx1YWUzMFx1YjI5NFx1YjM3MCBcdWI0ZGNcdWIyOTQgXHViZTQ0XHVjNmE5XHVjNzQwIGkralx1Yzc3NFx1YjJlNC4gXHVjMjFjXHVjNzA0XHViMjk0IDFcdWJkODBcdWQxMzAgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ2MDRcdWM3YWMgXHVjNzkwXHViOGNjXHVhZDZjXHVjODcwXHVjNWQwIFx1YzgwMFx1YzdhNVx1YjQxYyBcdWM4MTBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMGFjXHVjNmE5XHVjNzkwXHViOTdjIFx1YjBiNFx1YjliY1x1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4MTVcdWI4MmNcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWJlNDRcdWM2YTlcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MDBcdWM3YTVcdWI0MWMgXHVjODEwXHVjMjE4XHVjNzU4IFx1YzIxOCBuICgyICZsZTsgbiAmbGU7IDEwMDApIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODEwXHVjMjE4IHM8c3ViPmk8XC9zdWI+XHVhYzAwIFx1ZDYwNFx1YzdhYyBcdWM3OTBcdWI4Y2NcdWFkNmNcdWM4NzBcdWM1ZDAgXHVjODAwXHVjN2E1XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOygwICZsZTsgczxzdWI+aTxcL3N1Yj4gJmxlOyAxLDAwMCwwMDApIFx1YjQ1MCBcdWM4MTBcdWMyMThcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTBcdWMyMThcdWI5N2MgXHViMGI0XHViOWJjXHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1YzgxNVx1YjgyY1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjJm5ic3A7XHVjNzc0XHViM2Q5IFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1Yzc3NFx1YjNkOVx1Yzc0NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBpXHViYzg4XHVjOWY4IFx1YzgxMFx1YzIxOFx1Yjk3YyBqXHViYzg4XHVjOWY4XHViODVjIFx1YzYyZVx1YWUzNCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgaSBqXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNDMyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUmFua2xpc3QgU29ydGluZyIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBnaXZlbiB0aGUgc2NvcmVzIG9mIHNldmVyYWwgcGxheWVycyBpbiBhIGNvbXBldGl0aW9uLiBZb3VyIHRhc2sgaXMgdG8gY3JlYXRlIGEgcmFua2xpc3Qgb2YgdGhlIHBsYXllcnMsIHNvcnRlZCBpbiBkZWNyZWFzaW5nIG9yZGVyIGJ5IHNjb3JlLjxcL3A+XHJcblxyXG48cD5VbmZvcnR1bmF0ZWx5LCB0aGUgZGF0YSBzdHJ1Y3R1cmUgdXNlZCBmb3IgdGhlIGxpc3Qgb2YgcGxheWVycyBzdXBwb3J0cyBvbmx5IG9uZSBvcGVyYXRpb24sIHdoaWNoIG1vdmVzIGEgcGxheWVyIGZyb20gcG9zaXRpb24gaSB0byBwb3NpdGlvbiBqIHdpdGhvdXQgY2hhbmdpbmcgdGhlIHJlbGF0aXZlIG9yZGVyIG9mIG90aGVyIHBsYXllcnMuIElmIGkgJmd0OyBqLCB0aGUgcG9zaXRpb25zIG9mIHBsYXllcnMgYXQgcG9zaXRpb25zIGJldHdlZW4gaiBhbmQgaSAmbWludXM7IDEgaW5jcmVhc2UgYnkgMSwgb3RoZXJ3aXNlIGlmIGkgJmx0OyBqIHRoZSBwb3NpdGlvbnMgb2YgcGxheWVycyBhdCBwb3NpdGlvbnMgYmV0d2VlbiBpICsgMSBhbmQgaiBkZWNyZWFzZSBieSAxLjxcL3A+XHJcblxyXG48cD5UaGlzIG9wZXJhdGlvbiB0YWtlcyBpIHN0ZXBzIHRvIGxvY2F0ZSB0aGUgcGxheWVyIHRvIGJlIG1vdmVkLCBhbmQgaiBzdGVwcyB0byBsb2NhdGUgdGhlIHBvc2l0aW9uIHdoZXJlIGhlIG9yIHNoZSBpcyBtb3ZlZCB0bywgc28gdGhlIG92ZXJhbGwgY29zdCBvZiBtb3ZpbmcgYSBwbGF5ZXIgZnJvbSBwb3NpdGlvbiBpIHRvIHBvc2l0aW9uIGogaXMgaSArIGouIEhlcmUsIHBvc2l0aW9ucyBhcmUgbnVtYmVyZWQgc3RhcnRpbmcgd2l0aCAxLjxcL3A+XHJcblxyXG48cD5EZXRlcm1pbmUgYSBzZXF1ZW5jZSBvZiBtb3ZlcyB0byBjcmVhdGUgdGhlIHJhbmtsaXN0IHN1Y2ggdGhhdCB0aGUgc3VtIG9mIHRoZSBjb3N0cyBvZiB0aGUgbW92ZXMgaXMgbWluaW1pemVkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIGNvbnRhaW5zIG4gKDIgJmxlOyBuICZsZTsgMTAwMCksIHRoZSBudW1iZXIgb2YgcGxheWVycy4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIG4gbGluZXMgY29udGFpbnMgb25lIG5vbi1uZWdhdGl2ZSBpbnRlZ2VyIHNpICgwICZsZTsgc2kgJmxlOyAxLDAwMCwwMDApLCB0aGUgc2NvcmVzIG9mIHRoZSBwbGF5ZXJzIGluIHRoZSBjdXJyZW50IG9yZGVyLiBZb3UgbWF5IGFzc3VtZSB0aGF0IGFsbCBzY29yZXMgYXJlIGRpc3RpbmN0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIHRoZSBcdWZiMDFyc3QgbGluZSBvZiB0aGUgb3V0cHV0IHByaW50IHRoZSBudW1iZXIgb2YgbW92ZXMgdXNlZCB0byBjcmVhdGUgdGhlIHJhbmtsaXN0LiBUaGUgZm9sbG93aW5nIGxpbmVzIHNob3VsZCBzcGVjaWZ5IHRoZSBtb3ZlcyBpbiB0aGUgb3JkZXIgaW4gd2hpY2ggdGhleSBhcmUgYXBwbGllZC4gRWFjaCBtb3ZlIHNob3VsZCBiZSBkZXNjcmliZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgdHdvIGludGVnZXJzIGkgYW5kIGosIHdoaWNoIG1lYW5zIHRoYXQgdGhlIHBsYXllciBhdCBwb3NpdGlvbiBpIGlzIG1vdmVkIHRvIHBvc2l0aW9uIGouIFRoZSBudW1iZXJzIGkgYW5kIGogbXVzdCBiZSBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2007 2번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: onjo0127