sort

프로그램 명: coci_sort

제한시간: 1 초

다음 정렬 알고리즘을 고려해보자:

reverse-sort(순열 A)  
       while(A가 감소하지 않는 순서일 때까지)  
               A를 slope의 수가 최소가 되도록 분할 
               길이가 1보다 큰 모든 slope에 대해 
                       reverse(slope)

slope는 A의 감소하면서 연속적인 부분수열로 정의한다. reverse함수는 slope의 원소들의 순서를 뒤집는 과정을 수행한다. 당신에게 최소 개수의 slope로 분할하면 slope의 길이가 모두 짝수가 되는 처음 N개의 자연수(1~N 까지의 자연수)로 이루어진 순열이 주어질 것이다.

주어진 순열을 reverse-sort했을때 reverse가 몇번 호출되는지 구하여라.

입력

첫번째 줄에는 양의 정수 N (2 ≤ N ≤ 100 000)이 주어진다.
두번째 줄에는 정렬되어야하는 처음 N개의 자연수로 이루어진 순열이 주어진다.

출력

reverse함수가 호출된 횟수를 출력한다.

Consider the following sorting algorithm:

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

A slope is defined as a decreasing consecutive subsequence of a. The reverse procedure will reverse the order of the elements in a slope.

You are given a permutation of the first N natural numbers whose slopes all have even length when partitioned for the first time. Determine the total number of times reverse is called to reverse-sort the given permutation.

입력

The first line of input contains the positive integer N (2 ≤ N ≤ 100 000).
The second line of input contains a permutation of the first N natural numbers that needs to be sorted.

출력

The only line of output must contain the number of times that reverse is called.

입출력 예

input

2
2 1

output

1

input

4
4 3 2 1

output

1

input

4
3 1 4 2

output
3

출처:coci 2011 contest1 5/6
번역:august14

[질/답] [제출 현황] [푼 후(1)]

[ 채 점 ] [홈으로] [뒤 로]