시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 566 330 262 69.496%

문제

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

터보소트는 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+XHVjMTM4IFx1YmM4OFx1YzlmOCZuYnNwO1x1YjJlOFx1YWNjNFx1YjI5NCBcdWMyMmJcdWM3OTAgMlx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjYzNlXHVjNzQwIFx1ZDZjNFx1YzVkMCwgXHViYzE0XHViODVjIFx1YzU1ZVx1Yzc1OCBcdWMyMmJcdWM3OTBcdWM2NDAgXHVjNzA0XHVjZTU4XHViOTdjIFx1YmMxNFx1YWZiOFx1YzViNFx1YWMwMFx1YmE3NFx1YzExYywgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNjI0XHVhYzhjIFx1YmMxNFx1YWZiY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViMTI0IFx1YmM4OFx1YzlmOCBcdWIyZThcdWFjYzRcdWIyOTQmbmJzcDtcdWMyMmJcdWM3OTAgTi0xXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWNjM2VcdWM3NDAgXHViMmU0XHVjNzRjXHVjNWQwLCBcdWJjMTRcdWI4NWMgXHViNGE0XHVjNzU4IFx1YzIyYlx1Yzc5MFx1YzY0MCBcdWM3MDRcdWNlNThcdWI5N2MgXHViYzE0XHVhZmI4XHViYTc0XHVjMTFjLCBcdWI0YTRcdWM1ZDBcdWMxMWMgMlx1YmM4OFx1YzlmOCBcdWM3MDRcdWNlNThcdWM1ZDAgXHVjNjI0XHVhYzhjIFx1YmMxNFx1YWZiY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViMmU0XHVjMTJmIFx1YmM4OFx1YzlmOCBcdWIyZThcdWFjYzRcdWIzYzQgXHVjNzA0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWMyZGRcdWM3M2NcdWI4NWMgXHVkNTU4XHViYTc0IFx1YjQxOFx1YWNlMCBcdWM3NzRcdWI5N2MgTlx1YmM4OCBcdWJjMThcdWJjZjVcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzgxNVx1YjlhY1x1ZDU1OFx1YmE3NCwgXHVkNjQwXHVjMjE4XHViYzg4XHVjOWY4IFx1YjJlOFx1YWNjNFx1Yzc3NFx1YmE3NCwgXHVjNTQ0XHVjOWMxXHVhZTRjXHVjOWMwIFx1YWNlMFx1Yjk3NFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjMjJiXHVjNzkwIFx1YzkxMSBcdWM4MWNcdWM3N2MgXHVjNzkxXHVjNzQwIFx1YzIxOFx1Yjk3YyBcdWFjZTBcdWI5NzggXHViMmU0XHVjNzRjXHVjNWQwLCBcdWFkZjhcdWFjODNcdWM3NDQgXHVjNzc4XHVjODExXHVkNTVjIFx1YzIyYlx1Yzc5MFx1YzY0MCBcdWM3MDRcdWNlNThcdWI5N2MgXHViYzE0XHVhZmI4XHViYTc0XHVjMTFjIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWM3MDRcdWNlNThcdWI4NWMgXHVjNzc0XHViM2Q5XHVjMmRjXHVkMGE0XHVhY2UwLCBcdWM5ZGRcdWMyMThcdWJjODhcdWM5ZjggXHViMmU4XHVhY2M0XHVjNzdjXHViNTRjXHViMjk0LCBcdWM4MWNcdWM3N2MgXHVkMDcwIFx1YzIxOFx1Yjk3YyBcdWFjZTBcdWI5NzggXHViMmU0XHVjNzRjXHVjNWQwIFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWM3NzRcdWIzZDlcdWMyZGNcdWQwYTRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhODVcdWM2YjBcdWIyOTQgXHVjNzc0XHViNTRjLCBcdWFjMDEgXHViMmU4XHVhY2M0XHVjNWQwXHVjMTFjIFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHViYTg3IFx1YmM4OCBcdWJjMTRcdWFmYjhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+MVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1Y2QxZCBOXHVhYzFjXHVjNzU4IFx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYzMwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1ZDEzMFx1YmNmNCBcdWMxOGNcdWQyYjhcdWM3NTggXHVhYzAxIFx1YjJlOFx1YWNjNFx1YzVkMFx1YzExYywgXHVjMjJiXHVjNzkwXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWJhODcgXHViYzg4XHVjNTI5IFx1YmMxNFx1YWZiOFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAxMDAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViYTcwLCBcdWJjMzBcdWM1ZjRcdWM3NTggXHVkMDZjXHVhZTMwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjgmbmJzcDtcdWM5MDRcdWJkODBcdWQxMzAgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCBOXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjMjE4XHVhYzAwIFx1YzkxMVx1YmNmNSBcdWM1YzZcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjMjJiXHVjNzkwXHVhYzAwIFx1Y2MyOFx1Yjg0MFx1YjMwMFx1Yjg1YyBcdWJjMzBcdWM1ZjRcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjI5NCBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1YjJlOFx1YWNjNFx1YzVkMFx1YzExYyBcdWMyMmJcdWM3OTBcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YmE4NyBcdWJjODggXHViYzE0XHVhZmI4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjZDFkIE5cdWM5MDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMDA2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVFVSQk8iLCJkZXNjcmlwdGlvbiI6IjxwPkZyYW5lIGhhcyBiZWVuIGdpdmVuIHRoZSB0YXNrIG9mIHNvcnRpbmcgYW4gYXJyYXkgb2YgbnVtYmVycy4gVGhlIGFycmF5IGNvbnNpc3RzIG9mIE4gaW50ZWdlcnMsIGVhY2ggYmV0d2VlbiAxIGFuZCBOIChpbmNsdXNpdmUpLCB3aXRoIGVhY2ggb2YgdGhvc2UgYXBwZWFyaW5nIGV4YWN0bHkgb25jZSBpbiB0aGUgYXJyYXkuIEZyYW5lIGhhcyBjb21lIHVwIHdpdGggdGhlIGZvbGxvd2luZyBzb3J0aW5nIGFsZ29yaXRobSB3aGljaCBvcGVyYXRlcyBpbiBOIHBoYXNlcywgYW5kIG5hbWVkIGl0IHR1cmJvc29ydDombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5JbiB0aGUgZmlyc3QgcGhhc2UsIHRoZSBudW1iZXIgMSBpcyBtb3ZlZCB0byBwb3NpdGlvbiAxIGJ5IHJlcGVhdGVkbHkgc3dhcHBpbmcgY29uc2VjdXRpdmUgZWxlbWVudHMuJm5ic3A7PFwvbGk+XHJcblx0PGxpPkluIHRoZSBzZWNvbmQgcGhhc2UsIHRoZSBudW1iZXIgTiBpcyBtb3ZlZCB0byBwb3NpdGlvbiBOIGluIHRoZSBzYW1lIG1hbm5lci4mbmJzcDs8XC9saT5cclxuXHQ8bGk+SW4gdGhlIHRoaXJkIHBoYXNlLCB0aGUgbnVtYmVyIDIgaXMgbW92ZWQgdG8gcG9zaXRpb24gMi4mbmJzcDs8XC9saT5cclxuXHQ8bGk+SW4gdGhlIGZvdXJ0aCBwaGFzZSwgdGhlIG51bWJlciBOJm1pbnVzOzEgaXMgbW92ZWQgdG8gcG9zaXRpb24gTiZtaW51czsxLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5BbmQgc28gb24uJm5ic3A7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SW4gb3RoZXIgd29yZHMsIHdoZW4gdGhlIG51bWJlciBvZiB0aGUgcGhhc2UgaXMgb2RkLCBGcmFuZSB3aWxsIGNob29zZSB0aGUgc21hbGxlc3QgbnVtYmVyIG5vdCB5ZXQgY2hvc2VuLCBhbmQgbW92ZSBpdCB0byBpdHMgZmluYWwgcG9zaXRpb24uIEluIGV2ZW4gcGhhc2VzIGhlIGNob29zZXMgdGhlIGxhcmdlc3QgbnVtYmVyIG5vdCB5ZXQgY2hvc2VuLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gd2hpY2gsIGdpdmVuIHRoZSBpbml0aWFsIGFycmF5LCBvdXRwdXQgdGhlIG51bWJlciBvZiBzd2FwcyBpbiBlYWNoIHBoYXNlIG9mIHRoZSBhbGdvcml0aG0uJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMTAwMDAwKSwgdGhlIG51bWJlciBvZiBlbGVtZW50cyBpbiB0aGUgYXJyYXkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIGFuIGludGVnZXIgYmV0d2VlbiAxIGFuZCBOIChpbmNsdXNpdmUpLCB0aGUgYXJyYXkgdG8gYmUgc29ydGVkLiBUaGUgYXJyYXkgd2lsbCBjb250YWluIG5vIGR1cGxpY2F0ZXMuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggb2YgdGhlIE4gcGhhc2VzLCBvdXRwdXQgdGhlIG51bWJlciBvZiBzd2FwcyBvbiBhIHNpbmdsZSBsaW5lLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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