레이팅 미적용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.
The first line of input contains the positive integer \(N\) (\(2 \le N \le 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.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Test 1 | 10점 | None |
Test 2 | 10점 | None |
Test 3 | 10점 | None |
Test 4 | 10점 | None |
Test 5 | 10점 | None |
Test 6 | 10점 | None |
Test 7 | 10점 | None |
Test 8 | 10점 | None |
Test 9 | 10점 | None |
Test 10 | 10점 | None |
2
2 114
4 3 2 114
3 1 4 23