감소 구간 정렬

다음 정렬 알고리즘을 생각하자.

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가 호출되는 총 횟수를 출력한다.