퀵 소트 cnt++

아래 C++ 코드는 서로 다른 양의 정수 $N$개를 정렬한다.

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;
}

서로 다른 자연수 $N$개로 이루어진 배열 A가 주어질 때, 이 배열을 sort 함수로 정렬한 뒤 cnt에 들어 있는 값을 구하는 프로그램을 작성하시오.

첫째 줄에 $N$이 주어진다 ($1 \le N \le 500000$). 둘째 줄에는 배열 A에 들어 있는 수가 공백으로 구분되어 주어진다. 주어지는 수는 $1$부터 $N$까지의 수로 이루어진 순열이다.

입력으로 주어진 배열을 sort 함수로 정렬했을 때 cnt에 들어 있는 값을 출력한다.