P7629 [COCI 2011/2012 #1] SORT

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 contiguous subsequence of `a`, and `reverse()` reverses a segment of the sequence. You are given a permutation of $1$ to $N$. It is guaranteed that, in the first partition, the length of every `slope` is even. Determine how many times `reverse(slope)` will be called if this sorting algorithm is used to sort the given permutation.

The first line contains a positive integer $N$. The second line contains $N$ distinct positive integers, representing the permutation to be sorted.

Output one integer on a single line, the number of times `reverse(slope)` needs to be called.

#### Constraints For $100\%$ of the testdata, $2 \le N \le 10^5$. #### Explanation The score of this problem follows the original COCI settings, with a full score of $140$. Translated from **[COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #1](https://hsin.hr/coci/archive/2011_2012/contest1_tasks.pdf)** ___T5 SORT___. Translated by ChatGPT 5