감소 구간 정렬
시간 제한1초메모리 제한128 MB
최소 개수로 나눈 감소 구간의 길이가 모두 짝수인 순열이 주어질 때, 각 구간을 반복적으로 뒤집어 정렬할 때까지 reverse가 호출되는 총 횟수를 구합니다.
문제
다음 정렬 알고리즘을 생각하자.
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는 순열에서 값이 왼쪽에서 오른쪽으로 엄격히 감소하는 연속 부분 수열이다. reverse(slope)는 그 구간의 원소 순서를 뒤집는다.
1부터 N까지의 각 수가 한 번씩 등장하는 길이 N의 순열이 주어진다. 처음 순열을 최소 개수의 slope로 나누면 모든 slope의 길이는 짝수이다. 위 알고리즘이 순열을 비내림차순으로 정렬할 때 reverse가 호출되는 총 횟수를 구하시오.
입력
첫째 줄에 정수 N이 주어진다. (2 ≤ N ≤ 100,000)
둘째 줄에는 정렬해야 하는 순열이 주어진다.
출력
첫째 줄에 reverse가 호출되는 총 횟수를 출력한다.