COCI '11 Contest 1 #5 Sort

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem type

Consider the following sorting algorithm:

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)

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.

Input Specification

The first line of input contains the positive integer N (2 \leq N \leq 100\,000).

The second line of input contains a permutation of the first N natural numbers that needs to be sorted.

Output Specification

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

Sample Input 1

2
2 1

Sample Output 1

1

Sample Input 2

4
4 3 2 1

Sample Output 2

1

Sample Input 3

4
3 1 4 2

Sample Output 3

3

Comments

There are no comments at the moment.