求逆序对

题目描述

输入 ： n 个 1 ∼ 1 0 9 1∼10 9 范围内的整数，请输出包含多少逆序对。

输入格式 第一行一个整数 n。 接下来一行 n 个整数，含义如题意所述。

输出格式 一行一个整数。

样例

输入：

5

3 2 7 6 8

输出：

2

60tle：

#include <bits/stdc++.h>

using namespace std;

long long a[1000005];

int main() {

    long long n;
    cin>>n;
    for (int i=1; i<=n; i++){
        cin>>a[i];
    }
    int cnt=0;
    for (int i=1; i<=n; i++){
        for (int j=i+1; j<=n; j++){
            if (a[i]>a[j]){
                cnt++;
            }
        }
    }
    cout<<cnt;
    return 0;
    
}