Quick sort cnt++

Time limit2sMemory limit1024 MB

Summary

Count the comparisons made by a quicksort that splits each subarray around its middle-index pivot and recurses only on strictly smaller and larger elements.

Level: Medium7 of 10
Topics: Divide and conquer, Recursion, Sorting, Binary search
Solved: No attempts yet

Problem

The C++ code below sorts $N$ distinct positive integers.

long long cnt = 0;

vector<int> sort(vector<int> &a) {
    vector<int> less, greater;
    if (a.size() <= 1) return a;
    int pivot = a[(a.size() - 1) / 2];
    int n = a.size();
    for (int i = 0; i < n; i++) {
        cnt += 1;
        if (a[i] < pivot) {
            less.push_back(a[i]);
        } else if (a[i] > pivot) {
            greater.push_back(a[i]);
        }
    }
    sort(less); sort(greater);
    vector<int> ans;
    ans.insert(ans.end(), less.begin(), less.end());
    ans.push_back(pivot);
    ans.insert(ans.end(), greater.begin(), greater.end());
    return ans;
}

Given an array A of $N$ distinct positive integers, write a program that computes the value stored in cnt after A is sorted with this sort function.

Input

The first line contains $N$ ( $1 \le N \le 500000$ ). The second line contains the numbers in the array A, separated by spaces. The given numbers form a permutation of the integers from $1$ to $N$ .

Output

Print the value stored in cnt after the given array is sorted with the sort function.

Examples3

Example 1
Input
```
5
4 3 5 1 2
```
Expected output
```
11
```
Example 2
Input
```
1
1
```
Expected output
```
0
```
Example 3
Input
```
2
2 1
```
Expected output
```
2
```