시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 396 232 184 69.434%

문제

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

터보소트는 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+XHViYTg1XHVjNmIwXHViMjk0IFx1Yzc3NCBcdWI1NGMsIFx1YWMwMSBcdWIyZThcdWFjYzRcdWM1ZDBcdWMxMWMgXHVjMjJiXHVjNzkwXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWJhODcgXHViYzg4IFx1YmMxNFx1YWZiOFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD4xXHViZDgwXHVkMTMwIE5cdWFlNGNcdWM5YzAgXHVjZDFkIE5cdWFjMWNcdWM3NTggXHVjMjE4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJjMzBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkMTMwXHViY2Y0IFx1YzE4Y1x1ZDJiOFx1Yzc1OCBcdWFjMDEgXHViMmU4XHVhY2M0XHVjNWQwXHVjMTFjLCBcdWMyMmJcdWM3OTBcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YmE4NyBcdWJjODhcdWM1MjkgXHViYzE0XHVhZmI4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gTlx1Yzc0MCAxXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEwMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWJhNzAsIFx1YmMzMFx1YzVmNFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCZuYnNwO1x1YzkwNFx1YmQ4MFx1ZDEzMCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCAxXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIE5cdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWMyMThcdWFjMDAgXHVjOTExXHViY2Y1IFx1YzVjNlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YmMzMFx1YzVmNFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHViMmU4XHVhY2M0XHVjNWQwXHVjMTFjIFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHViYTg3IFx1YmM4OCBcdWJjMTRcdWFmYjhcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNkMWQgTlx1YzkwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwMDYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUVVJCTyIsImRlc2NyaXB0aW9uIjoiPHA+RnJhbmUgaGFzIGJlZW4gZ2l2ZW4gdGhlIHRhc2sgb2Ygc29ydGluZyBhbiBhcnJheSBvZiBudW1iZXJzLiBUaGUgYXJyYXkgY29uc2lzdHMgb2YgTiBpbnRlZ2VycywgZWFjaCBiZXR3ZWVuIDEgYW5kIE4gKGluY2x1c2l2ZSksIHdpdGggZWFjaCBvZiB0aG9zZSBhcHBlYXJpbmcgZXhhY3RseSBvbmNlIGluIHRoZSBhcnJheS4gRnJhbmUgaGFzIGNvbWUgdXAgd2l0aCB0aGUgZm9sbG93aW5nIHNvcnRpbmcgYWxnb3JpdGhtIHdoaWNoIG9wZXJhdGVzIGluIE4gcGhhc2VzLCBhbmQgbmFtZWQgaXQgdHVyYm9zb3J0OiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkluIHRoZSBmaXJzdCBwaGFzZSwgdGhlIG51bWJlciAxIGlzIG1vdmVkIHRvIHBvc2l0aW9uIDEgYnkgcmVwZWF0ZWRseSBzd2FwcGluZyBjb25zZWN1dGl2ZSBlbGVtZW50cy4mbmJzcDs8XC9saT5cclxuXHQ8bGk+SW4gdGhlIHNlY29uZCBwaGFzZSwgdGhlIG51bWJlciBOIGlzIG1vdmVkIHRvIHBvc2l0aW9uIE4gaW4gdGhlIHNhbWUgbWFubmVyLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5JbiB0aGUgdGhpcmQgcGhhc2UsIHRoZSBudW1iZXIgMiBpcyBtb3ZlZCB0byBwb3NpdGlvbiAyLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5JbiB0aGUgZm91cnRoIHBoYXNlLCB0aGUgbnVtYmVyIE4mbWludXM7MSBpcyBtb3ZlZCB0byBwb3NpdGlvbiBOJm1pbnVzOzEuJm5ic3A7PFwvbGk+XHJcblx0PGxpPkFuZCBzbyBvbi4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5JbiBvdGhlciB3b3Jkcywgd2hlbiB0aGUgbnVtYmVyIG9mIHRoZSBwaGFzZSBpcyBvZGQsIEZyYW5lIHdpbGwgY2hvb3NlIHRoZSBzbWFsbGVzdCBudW1iZXIgbm90IHlldCBjaG9zZW4sIGFuZCBtb3ZlIGl0IHRvIGl0cyBmaW5hbCBwb3NpdGlvbi4gSW4gZXZlbiBwaGFzZXMgaGUgY2hvb3NlcyB0aGUgbGFyZ2VzdCBudW1iZXIgbm90IHlldCBjaG9zZW4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaCwgZ2l2ZW4gdGhlIGluaXRpYWwgYXJyYXksIG91dHB1dCB0aGUgbnVtYmVyIG9mIHN3YXBzIGluIGVhY2ggcGhhc2Ugb2YgdGhlIGFsZ29yaXRobS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDAwMDApLCB0aGUgbnVtYmVyIG9mIGVsZW1lbnRzIGluIHRoZSBhcnJheS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgYW4gaW50ZWdlciBiZXR3ZWVuIDEgYW5kIE4gKGluY2x1c2l2ZSksIHRoZSBhcnJheSB0byBiZSBzb3J0ZWQuIFRoZSBhcnJheSB3aWxsIGNvbnRhaW4gbm8gZHVwbGljYXRlcy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBvZiB0aGUgTiBwaGFzZXMsIG91dHB1dCB0aGUgbnVtYmVyIG9mIHN3YXBzIG9uIGEgc2luZ2xlIGxpbmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

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