10090.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

#define MAXN 1000050
int n,arr[MAXN],tmp[MAXN];
long long ans=0;


void merge(int low, int mid, int high){
    int l_idx = low;
    int r_idx = mid;
    int t_idx = low;
    while(l_idx < mid && r_idx < high){
        if(arr[l_idx] < arr[r_idx]) tmp[t_idx++] = arr[l_idx++];
        else {
            tmp[t_idx++] = arr[r_idx++];
            ans += mid - l_idx;
        }
    }
    while(l_idx < mid) tmp[t_idx++] = arr[l_idx++];
    while(r_idx < high) tmp[t_idx++] = arr[r_idx++];

    for(int i=low ; i<high ; i++) arr[i] = tmp[i]; 


}

void merge_sort(int low, int high){
    if(low == high - 1) return;
    int mid = (low + high)/2;

    merge_sort(low, mid);
    merge_sort(mid, high);
    merge(low, mid, high);

}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    cin >> n;
    for(int i=1 ; i<=n ; i++) cin >> arr[i];
    
    merge_sort(1,n+1);
    cout << ans;

}