Problem 9: Fenwick Tree for Inversion Count

Problem Statement: Given an array of integers, count the number of inversions using a Fenwick (Binary Indexed) Tree.

Input

The first line contains n, the number of elements. The next line contains n space-separated integers.

Output

Print the total number of inversions in the array.

Examples


Input:
5
2 3 8 6 1

Output:
5

Solution Explanation

Method 1: Use a Fenwick tree to count the number of elements already seen that are smaller than the current element, iterating from right to left. Method 2: Use a modified merge sort algorithm to count inversions, which naturally divides and counts while merging.

Solution in C++


#include 
#include 
#include 
using namespace std;

struct Fenwick{
    int n;
    vector tree;
    Fenwick(int n): n(n) {tree.assign(n+1, 0);}
    void update(int i, int delta){
        for(; i <= n; i += i & -i)
            tree[i] += delta;
    }
    int query(int i){
        int sum = 0;
        for(; i > 0; i -= i & -i)
            sum += tree[i];
        return sum;
    }
};

int main(){
    int n;
    cin >> n;
    vector arr(n), temp;
    for(int i=0;i> arr[i];
        temp.push_back(arr[i]);
    }
    sort(temp.begin(), temp.end());
    temp.erase(unique(temp.begin(), temp.end()), temp.end());
    Fenwick fenw(temp.size());
    long long inversions = 0;
    for(int i=n-1; i>=0; i--){
        int pos = lower_bound(temp.begin(), temp.end(), arr[i]) - temp.begin() + 1;
        inversions += fenw.query(pos-1);
        fenw.update(pos, 1);
    }
    cout << inversions;
    return 0;
}