시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 124 43 31 40.789%

문제

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

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

4
3 1 4 2

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjI4MzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTVcdWI4MmMiLCJkZXNjcmlwdGlvbiI6IlxyXG48cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWI4MmMgXHVjNTRjXHVhY2UwXHViOWFjXHVjOTk4XHVjNzQ0IFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxucmV2ZXJzZS1zb3J0KHNlcXVlbmNlIGEpXHJcbiAgICB3aGlsZSAoQSBpcyBub3QgaW4gbm9uZGVjcmVhc2luZyBvcmRlcilcclxuICAgICAgICBwYXJ0aXRpb24gYSBpbnRvIHRoZSBtaW5pbXVtIG51bWJlciBvZiBzbG9wZXNcclxuICAgICAgICBmb3IgZXZlcnkgc2xvcGUgd2l0aCBsZW5ndGggZ3JlYXRlciB0aGFuIG9uZVxyXG4gICAgICAgICAgICByZXZlcnNlKHNsb3BlKTxcL3ByZT5cclxuXHJcbjxwPlxyXG5cdFx1YzVlY1x1YWUzMFx1YzExYyBzbG9wZVx1Yjc4MCBcdWFjMTBcdWMxOGNcdWQ1NThcdWIyOTQgYVx1Yzc1OCBcdWM1ZjBcdWMxOGQgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNFx1Yzc3NFx1YjJlNC4gcmV2ZXJzZVx1YjI5NCBcdWFkZjggXHVhZDZjXHVhYzA0XHVjNzU4IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWI0YTRcdWM5ZDFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdDFcdWJkODBcdWQxMzAgTlx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhZTM4XHVjNzc0XHVhYzAwIE5cdWM3NzggXHVjMjFjXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjYzk4XHVjNzRjXHVjNWQwIFx1YzIxY1x1YzVmNFx1Yzc1OCBzbG9wZVx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHViYWE4XHViNDUwIFx1YzlkZFx1YzIxOFx1Yzc3NFx1YjJlNC4gcmV2ZXJzZVx1Yjk3YyBcdWJhODcgXHViYzg4IFx1ZDYzOFx1Y2Q5Y1x1ZDU1OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMTAwLDAwMCkgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTVcdWI4MmNcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzIxY1x1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCByZXZlcnNlXHViOTdjIFx1YmE4NyBcdWJjODggXHVkNjM4XHVjZDljXHVkNTU4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODMyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU09SVCIsImRlc2NyaXB0aW9uIjoiPHA+Q29uc2lkZXIgdGhlIGZvbGxvd2luZyBzb3J0aW5nIGFsZ29yaXRobTo8XC9wPlxyXG5cclxuPHByZT5cclxucmV2ZXJzZS1zb3J0KHNlcXVlbmNlIGEpXHJcbiAgICB3aGlsZSAoQSBpcyBub3QgaW4gbm9uZGVjcmVhc2luZyBvcmRlcilcclxuICAgICAgICBwYXJ0aXRpb24gYSBpbnRvIHRoZSBtaW5pbXVtIG51bWJlciBvZiBzbG9wZXNcclxuICAgICAgICBmb3IgZXZlcnkgc2xvcGUgd2l0aCBsZW5ndGggZ3JlYXRlciB0aGFuIG9uZVxyXG4gICAgICAgICAgICByZXZlcnNlKHNsb3BlKTxcL3ByZT5cclxuXHJcbjxwPkEgc2xvcGUgaXMgZGVmaW5lZCBhcyBhIGRlY3JlYXNpbmcgY29uc2VjdXRpdmUgc3Vic2VxdWVuY2Ugb2YgYS4gVGhlIHJldmVyc2UgcHJvY2VkdXJlIHdpbGwgcmV2ZXJzZSB0aGUgb3JkZXIgb2YgdGhlIGVsZW1lbnRzIGluIGEgc2xvcGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPllvdSBhcmUgZ2l2ZW4gYSBwZXJtdXRhdGlvbiBvZiB0aGUgZmlyc3QgTiBuYXR1cmFsIG51bWJlcnMgd2hvc2Ugc2xvcGVzIGFsbCBoYXZlIGV2ZW4gbGVuZ3RoIHdoZW4gcGFydGl0aW9uZWQgZm9yIHRoZSBmaXJzdCB0aW1lLiBEZXRlcm1pbmUgdGhlIHRvdGFsIG51bWJlciBvZiB0aW1lcyByZXZlcnNlIGlzIGNhbGxlZCB0byByZXZlcnNlLXNvcnQgdGhlIGdpdmVuIHBlcm11dGF0aW9uLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTiAoMiAmbGU7IE4gJmxlOyAxMDAgMDAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgcGVybXV0YXRpb24gb2YgdGhlIGZpcnN0IE4gbmF0dXJhbCBudW1iZXJzIHRoYXQgbmVlZHMgdG8gYmUgc29ydGVkLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgbnVtYmVyIG9mIHRpbWVzIHRoYXQgcmV2ZXJzZSBpcyBjYWxsZWQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==