14894번 - 퀵 소트 cnt++

구사과는 N개의 서로 다른 양의 정수를 정렬하기 위해 아래와 같은 C++ 코드를 작성했다.

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 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 배열 A에 들어있는 수가 공백으로 구분해 주어진다. 주어지는 수는 1부터 N까지의 수로 이루어진 순열이다.

입력으로 주어진 수를 sort 함수를 이용해 정렬했을 때, cnt에 들어있는 값을 출력한다.