시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB254694944.144%

문제

상근이는 다음과 같은 정렬 알고리즘을 만들었다.

reverse-sort(sequence a)
    while (A is not in nondecreasing order)
        partition a into the minimum number of slopes
        for every slope with length greater than one
            reverse(slope)

여기서 slope란 감소하는 a의 연속 부분 수열이다. reverse는 그 구간의 순서를 뒤집는다.

1부터 N으로 이루어진 길이가 N인 순열이 주어진다. 처음에 순열의 slope의 길이는 모두 짝수이다. reverse를 몇 번 호출하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 둘째 줄에는 정렬해야 하는 순열이 주어진다.

출력

첫째 줄에 reverse를 몇 번 호출하는지 출력한다.

예제 입력 1

2
2 1

예제 출력 1

1

예제 입력 2

4
4 3 2 1

예제 출력 2

1

예제 입력 3

4
3 1 4 2

예제 출력 3

3
W3sicHJvYmxlbV9pZCI6IjI4MzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTVcdWI4MmMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzgxNVx1YjgyYyBcdWM1NGNcdWFjZTBcdWI5YWNcdWM5OThcdWM3NDQgXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG5yZXZlcnNlLXNvcnQoc2VxdWVuY2UgYSlcclxuICAgIHdoaWxlIChBIGlzIG5vdCBpbiBub25kZWNyZWFzaW5nIG9yZGVyKVxyXG4gICAgICAgIHBhcnRpdGlvbiBhIGludG8gdGhlIG1pbmltdW0gbnVtYmVyIG9mIHNsb3Blc1xyXG4gICAgICAgIGZvciBldmVyeSBzbG9wZSB3aXRoIGxlbmd0aCBncmVhdGVyIHRoYW4gb25lXHJcbiAgICAgICAgICAgIHJldmVyc2Uoc2xvcGUpPFwvcHJlPlxyXG5cclxuPHA+XHVjNWVjXHVhZTMwXHVjMTFjIHNsb3BlXHViNzgwIFx1YWMxMFx1YzE4Y1x1ZDU1OFx1YjI5NCBhXHVjNzU4IFx1YzVmMFx1YzE4ZCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0XHVjNzc0XHViMmU0LiByZXZlcnNlXHViMjk0IFx1YWRmOCBcdWFkNmNcdWFjMDRcdWM3NTggXHVjMjFjXHVjMTFjXHViOTdjIFx1YjRhNFx1YzlkMVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+MVx1YmQ4MFx1ZDEzMCBOXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWFlMzhcdWM3NzRcdWFjMDAgTlx1Yzc3OCBcdWMyMWNcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWNjOThcdWM3NGNcdWM1ZDAgXHVjMjFjXHVjNWY0XHVjNzU4IHNsb3BlXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWJhYThcdWI0NTAgXHVjOWRkXHVjMjE4XHVjNzc0XHViMmU0LiByZXZlcnNlXHViOTdjIFx1YmE4NyBcdWJjODggXHVkNjM4XHVjZDljXHVkNTU4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMTAwLDAwMCkgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWI4MmNcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzIxY1x1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCByZXZlcnNlXHViOTdjIFx1YmE4NyBcdWJjODggXHVkNjM4XHVjZDljXHVkNTU4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyODMyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU09SVCIsImRlc2NyaXB0aW9uIjoiPHA+Q29uc2lkZXIgdGhlIGZvbGxvd2luZyBzb3J0aW5nIGFsZ29yaXRobTo8XC9wPlxyXG5cclxuPHByZT5cclxucmV2ZXJzZS1zb3J0KHNlcXVlbmNlIGEpXHJcbiAgICB3aGlsZSAoQSBpcyBub3QgaW4gbm9uZGVjcmVhc2luZyBvcmRlcilcclxuICAgICAgICBwYXJ0aXRpb24gYSBpbnRvIHRoZSBtaW5pbXVtIG51bWJlciBvZiBzbG9wZXNcclxuICAgICAgICBmb3IgZXZlcnkgc2xvcGUgd2l0aCBsZW5ndGggZ3JlYXRlciB0aGFuIG9uZVxyXG4gICAgICAgICAgICByZXZlcnNlKHNsb3BlKTxcL3ByZT5cclxuXHJcbjxwPkEgc2xvcGUgaXMgZGVmaW5lZCBhcyBhIGRlY3JlYXNpbmcgY29uc2VjdXRpdmUgc3Vic2VxdWVuY2Ugb2YgYS4gVGhlIHJldmVyc2UgcHJvY2VkdXJlIHdpbGwgcmV2ZXJzZSB0aGUgb3JkZXIgb2YgdGhlIGVsZW1lbnRzIGluIGEgc2xvcGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gYSBwZXJtdXRhdGlvbiBvZiB0aGUgZmlyc3QgTiBuYXR1cmFsIG51bWJlcnMgd2hvc2Ugc2xvcGVzIGFsbCBoYXZlIGV2ZW4gbGVuZ3RoIHdoZW4gcGFydGl0aW9uZWQgZm9yIHRoZSBmaXJzdCB0aW1lLiBEZXRlcm1pbmUgdGhlIHRvdGFsIG51bWJlciBvZiB0aW1lcyByZXZlcnNlIGlzIGNhbGxlZCB0byByZXZlcnNlLXNvcnQgdGhlIGdpdmVuIHBlcm11dGF0aW9uLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTiAoMiAmbGU7IE4gJmxlOyAxMDAgMDAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgcGVybXV0YXRpb24gb2YgdGhlIGZpcnN0IE4gbmF0dXJhbCBudW1iZXJzIHRoYXQgbmVlZHMgdG8gYmUgc29ydGVkLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgbnVtYmVyIG9mIHRpbWVzIHRoYXQgcmV2ZXJzZSBpcyBjYWxsZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #1 5번