시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 499 285 228 68.675%

문제

명우가 소트 알고리즘을 하나 발명했다. 이 알고리즘의 이름은 터보소트이다. 

터보소트는 1부터 N까지 총 N개의 수가 섞여있을 때만 사용할 수 있으며, 다음과 같이 N단계로 이루어져 있다.

  • 첫 번째 단계에서 숫자 1의 위치를 찾는다. 그 다음 바로 앞의 숫자와 위치를 바꾸어가면서, 1이 제일 앞에 오게 바꾼다.
  • 두 번째 단계에서는 숫자 N의 위치를 찾는다. 그 다음 바로 뒤의 숫자와 위치를 바꾸어가면서, N이 제일 마지막에 오게 바꾼다.
  • 세 번째 단계은 숫자 2의 위치를 찾은 후에, 바로 앞의 숫자와 위치를 바꾸어가면서, 두 번째 위치에 오게 바꾼다.
  • 네 번째 단계은 숫자 N-1의 위치를 찾은 다음에, 바로 뒤의 숫자와 위치를 바꾸면서, 뒤에서 2번째 위치에 오게 바꾼다.
  • 다섯 번째 단계도 위와 같은 식으로 하면 되고 이를 N번 반복하는 것이다.

정리하면, 홀수번째 단계이면, 아직까지 고르지 않은 숫자 중 제일 작은 수를 고른 다음에, 그것을 인접한 숫자와 위치를 바꾸면서 올바른 위치로 이동시키고, 짝수번째 단계일때는, 제일 큰 수를 고른 다음에 위치를 이동시키는 것이다.

명우는 이때, 각 단계에서 숫자의 위치를 몇 번 바꾸는지 구하려고 한다.

1부터 N까지 총 N개의 수로 이루어진 배열이 주어졌을 때, 터보 소트의 각 단계에서, 숫자의 위치를 몇 번씩 바꾸는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이며, 배열의 크기이다.

둘째 줄부터 N개의 줄에는 1보다 크거나 같고, N보다 작거나 같은 수가 중복 없이 주어진다. 이 숫자가 차례대로 배열에 포함되어 있는 수이다.

출력

각 단계에서 숫자의 위치를 몇 번 바꾸는지 출력한다. 총 N줄을 출력해야 한다.

예제 입력 1

3
2
1
3

예제 출력 1

1
0
0

예제 입력 2

5
5
4
3
2
1

예제 출력 2

4
3
2
1
0

예제 입력 3

7
5
4
3
7
1
2
6

예제 출력 3

4
2
3
0
2
1
0
W3sicHJvYmxlbV9pZCI6IjMwMDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQxMzBcdWJjZjRcdWMxOGNcdWQyYjgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YmE4NVx1YzZiMFx1YWMwMCBcdWMxOGNcdWQyYjggXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWJjMWNcdWJhODVcdWQ1ODhcdWIyZTQuIFx1Yzc3NCBcdWM1NGNcdWFjZTBcdWI5YWNcdWM5OThcdWM3NTggXHVjNzc0XHViOTg0XHVjNzQwIFx1ZDEzMFx1YmNmNFx1YzE4Y1x1ZDJiOFx1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVkMTMwXHViY2Y0XHVjMThjXHVkMmI4XHViMjk0IDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWNkMWQgTlx1YWMxY1x1Yzc1OCBcdWMyMThcdWFjMDAgXHVjMTFlXHVjNWVjXHVjNzg4XHVjNzQ0IFx1YjU0Y1x1YjljYyBcdWMwYWNcdWM2YTlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBOXHViMmU4XHVhY2M0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWIyZThcdWFjYzRcdWM1ZDBcdWMxMWMgXHVjMjJiXHVjNzkwIDFcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1Y2MzZVx1YjI5NFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWJjMTRcdWI4NWMgXHVjNTVlXHVjNzU4IFx1YzIyYlx1Yzc5MFx1YzY0MCBcdWM3MDRcdWNlNThcdWI5N2MgXHViYzE0XHVhZmI4XHVjNWI0XHVhYzAwXHViYTc0XHVjMTFjLCAxXHVjNzc0IFx1YzgxY1x1Yzc3YyBcdWM1NWVcdWM1ZDAgXHVjNjI0XHVhYzhjIFx1YmMxNFx1YWZiY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWIyZThcdWFjYzRcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjMjJiXHVjNzkwIE5cdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1Y2MzZVx1YjI5NFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWJjMTRcdWI4NWMgXHViNGE0XHVjNzU4IFx1YzIyYlx1Yzc5MFx1YzY0MCBcdWM3MDRcdWNlNThcdWI5N2MgXHViYzE0XHVhZmI4XHVjNWI0XHVhYzAwXHViYTc0XHVjMTFjLCBOXHVjNzc0IFx1YzgxY1x1Yzc3YyBcdWI5YzhcdWM5YzBcdWI5YzlcdWM1ZDAgXHVjNjI0XHVhYzhjIFx1YmMxNFx1YWZiY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMTM4IFx1YmM4OFx1YzlmOCZuYnNwO1x1YjJlOFx1YWNjNFx1Yzc0MCBcdWMyMmJcdWM3OTAgMlx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjYzNlXHVjNzQwIFx1ZDZjNFx1YzVkMCwgXHViYzE0XHViODVjIFx1YzU1ZVx1Yzc1OCBcdWMyMmJcdWM3OTBcdWM2NDAgXHVjNzA0XHVjZTU4XHViOTdjIFx1YmMxNFx1YWZiOFx1YzViNFx1YWMwMFx1YmE3NFx1YzExYywgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNjI0XHVhYzhjIFx1YmMxNFx1YWZiY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViMTI0IFx1YmM4OFx1YzlmOCBcdWIyZThcdWFjYzRcdWM3NDAgXHVjMjJiXHVjNzkwIE4tMVx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjYzNlXHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YzVkMCwgXHViYzE0XHViODVjIFx1YjRhNFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWM2NDAgXHVjNzA0XHVjZTU4XHViOTdjIFx1YmMxNFx1YWZiOFx1YmE3NFx1YzExYywgXHViNGE0XHVjNWQwXHVjMTFjIDJcdWJjODhcdWM5ZjggXHVjNzA0XHVjZTU4XHVjNWQwIFx1YzYyNFx1YWM4YyBcdWJjMTRcdWFmYmNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjJlNFx1YzEyZiBcdWJjODhcdWM5ZjggXHViMmU4XHVhY2M0XHViM2M0IFx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjMmRkXHVjNzNjXHViODVjIFx1ZDU1OFx1YmE3NCBcdWI0MThcdWFjZTAgXHVjNzc0XHViOTdjIE5cdWJjODggXHViYzE4XHViY2Y1XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM4MTVcdWI5YWNcdWQ1NThcdWJhNzQsIFx1ZDY0MFx1YzIxOFx1YmM4OFx1YzlmOCBcdWIyZThcdWFjYzRcdWM3NzRcdWJhNzQsIFx1YzU0NFx1YzljMVx1YWU0Y1x1YzljMCBcdWFjZTBcdWI5NzRcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YzIyYlx1Yzc5MCBcdWM5MTEgXHVjODFjXHVjNzdjIFx1Yzc5MVx1Yzc0MCBcdWMyMThcdWI5N2MgXHVhY2UwXHViOTc4IFx1YjJlNFx1Yzc0Y1x1YzVkMCwgXHVhZGY4XHVhYzgzXHVjNzQ0IFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWMyMmJcdWM3OTBcdWM2NDAgXHVjNzA0XHVjZTU4XHViOTdjIFx1YmMxNFx1YWZiOFx1YmE3NFx1YzExYyBcdWM2MmNcdWJjMTRcdWI5NzggXHVjNzA0XHVjZTU4XHViODVjIFx1Yzc3NFx1YjNkOVx1YzJkY1x1ZDBhNFx1YWNlMCwgXHVjOWRkXHVjMjE4XHViYzg4XHVjOWY4IFx1YjJlOFx1YWNjNFx1Yzc3Y1x1YjU0Y1x1YjI5NCwgXHVjODFjXHVjNzdjIFx1ZDA3MCBcdWMyMThcdWI5N2MgXHVhY2UwXHViOTc4IFx1YjJlNFx1Yzc0Y1x1YzVkMCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjNzc0XHViM2Q5XHVjMmRjXHVkMGE0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYTg1XHVjNmIwXHViMjk0IFx1Yzc3NFx1YjU0YywgXHVhYzAxIFx1YjJlOFx1YWNjNFx1YzVkMFx1YzExYyBcdWMyMmJcdWM3OTBcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YmE4NyBcdWJjODggXHViYzE0XHVhZmI4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWNkMWQgTlx1YWMxY1x1Yzc1OCBcdWMyMThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmMzMFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWQxMzBcdWJjZjQgXHVjMThjXHVkMmI4XHVjNzU4IFx1YWMwMSBcdWIyZThcdWFjYzRcdWM1ZDBcdWMxMWMsIFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHViYTg3IFx1YmM4OFx1YzUyOSBcdWJjMTRcdWFmYjhcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBOXHVjNzQwIDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YmE3MCwgXHViYzMwXHVjNWY0XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4Jm5ic3A7XHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgTlx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzIxOFx1YWMwMCBcdWM5MTFcdWJjZjUgXHVjNWM2XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHViYzMwXHVjNWY0XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWIyZThcdWFjYzRcdWM1ZDBcdWMxMWMgXHVjMjJiXHVjNzkwXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWJhODcgXHViYzg4IFx1YmMxNFx1YWZiOFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2QxZCBOXHVjOTA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzAwNiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRVUkJPIiwiZGVzY3JpcHRpb24iOiI8cD5GcmFuZSBoYXMgYmVlbiBnaXZlbiB0aGUgdGFzayBvZiBzb3J0aW5nIGFuIGFycmF5IG9mIG51bWJlcnMuIFRoZSBhcnJheSBjb25zaXN0cyBvZiBOIGludGVnZXJzLCBlYWNoIGJldHdlZW4gMSBhbmQgTiAoaW5jbHVzaXZlKSwgd2l0aCBlYWNoIG9mIHRob3NlIGFwcGVhcmluZyBleGFjdGx5IG9uY2UgaW4gdGhlIGFycmF5LiBGcmFuZSBoYXMgY29tZSB1cCB3aXRoIHRoZSBmb2xsb3dpbmcgc29ydGluZyBhbGdvcml0aG0gd2hpY2ggb3BlcmF0ZXMgaW4gTiBwaGFzZXMsIGFuZCBuYW1lZCBpdCB0dXJib3NvcnQ6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+SW4gdGhlIGZpcnN0IHBoYXNlLCB0aGUgbnVtYmVyIDEgaXMgbW92ZWQgdG8gcG9zaXRpb24gMSBieSByZXBlYXRlZGx5IHN3YXBwaW5nIGNvbnNlY3V0aXZlIGVsZW1lbnRzLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5JbiB0aGUgc2Vjb25kIHBoYXNlLCB0aGUgbnVtYmVyIE4gaXMgbW92ZWQgdG8gcG9zaXRpb24gTiBpbiB0aGUgc2FtZSBtYW5uZXIuJm5ic3A7PFwvbGk+XHJcblx0PGxpPkluIHRoZSB0aGlyZCBwaGFzZSwgdGhlIG51bWJlciAyIGlzIG1vdmVkIHRvIHBvc2l0aW9uIDIuJm5ic3A7PFwvbGk+XHJcblx0PGxpPkluIHRoZSBmb3VydGggcGhhc2UsIHRoZSBudW1iZXIgTiZtaW51czsxIGlzIG1vdmVkIHRvIHBvc2l0aW9uIE4mbWludXM7MS4mbmJzcDs8XC9saT5cclxuXHQ8bGk+QW5kIHNvIG9uLiZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkluIG90aGVyIHdvcmRzLCB3aGVuIHRoZSBudW1iZXIgb2YgdGhlIHBoYXNlIGlzIG9kZCwgRnJhbmUgd2lsbCBjaG9vc2UgdGhlIHNtYWxsZXN0IG51bWJlciBub3QgeWV0IGNob3NlbiwgYW5kIG1vdmUgaXQgdG8gaXRzIGZpbmFsIHBvc2l0aW9uLiBJbiBldmVuIHBoYXNlcyBoZSBjaG9vc2VzIHRoZSBsYXJnZXN0IG51bWJlciBub3QgeWV0IGNob3Nlbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHdoaWNoLCBnaXZlbiB0aGUgaW5pdGlhbCBhcnJheSwgb3V0cHV0IHRoZSBudW1iZXIgb2Ygc3dhcHMgaW4gZWFjaCBwaGFzZSBvZiB0aGUgYWxnb3JpdGhtLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMDAwMCksIHRoZSBudW1iZXIgb2YgZWxlbWVudHMgaW4gdGhlIGFycmF5LiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyBhbiBpbnRlZ2VyIGJldHdlZW4gMSBhbmQgTiAoaW5jbHVzaXZlKSwgdGhlIGFycmF5IHRvIGJlIHNvcnRlZC4gVGhlIGFycmF5IHdpbGwgY29udGFpbiBubyBkdXBsaWNhdGVzLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIG9mIHRoZSBOIHBoYXNlcywgb3V0cHV0IHRoZSBudW1iZXIgb2Ygc3dhcHMgb24gYSBzaW5nbGUgbGluZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #2 4번

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