Proficient.
Put your skills to the test.

Problem summary

Given a permutation of 1…n, count pairs of positions i<j for which a[i]>a[j]. These are inversions: larger values appearing before smaller values.

Constraints

2 ≤ n ≤ 1000000; every value 1…n appears exactly once.

Worked example

Original statement sample.

7
4 2 7 1 5 6 3

10

Solution analysis

1. Process the permutation from left to right. When reading value v at zero-based position i, exactly i earlier values have been seen. If a Fenwick tree counts how many of them are at most v, then i−prefixCount(v) are larger than v and form inversions ending here.
2. Add that difference to the answer, then insert v into the tree by adding 1 at index v. Query before insertion so the current element is not counted as an earlier one. A Fenwick tree stores partial frequency sums and supports both operations in O(log n).
3. For the sample, the successive contributions are 0 for 4, 1 for 2, 0 for 7, 3 for 1, 1 for 5, 1 for 6, and 4 for 3. Their sum is 10. A sorted permutation contributes zero everywhere; reverse order contributes n(n−1)/2.
4. The values are already the index range 1…n, so coordinate compression is unnecessary. Frequencies fit in int, but the total can be 499999500000 for n=1000000, requiring long long.

Why it works

Each inversion has a unique right endpoint. The prefix frequency query counts exactly the earlier values not greater than the current value; subtracting from the number of earlier positions counts exactly its inversion partners. Summing over all right endpoints counts every inversion once.

Watch out. Use a 64-bit answer. Fenwick indices start at 1; index 0 would make the update loop fail to advance. Count earlier larger values, not all larger values in the permutation.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>tree(n+1,0);
    long long answer=0;
    for(int position=0;position<n;position++){
        int value;
        cin>>value;
        int notGreater=0;
        for(int index=value;index>0;index-=index&-index){
            notGreater+=tree[index];
        }
        // Every earlier greater value forms one inversion ending here.
        answer+=position-notGreater;
        for(int index=value;index<=n;index+=index&-index){
            tree[index]++;
        }
    }
    cout<<answer<<'\n';
}