HDU 1394 Minimum Inversion Number

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5010;
int N;
int c[maxn], a[maxn];

int lowbit(int x) {
    return x & (-x);
}

void add(int x, int val) {
    while(x <= N) {
        c[x] += val;
        x += lowbit(x);
    }
}

int getsum(int x) {
    int sum = 0;
    while(x > 0) {
        sum += c[x];
        x -= lowbit(x);
    }
    return sum;
}

int main() {
    while(~scanf("%d", &N)) {
        if(!N) break;
        memset(c, 0, sizeof(c));
        int ans = 0;
        for(int i = 1; i <= N; i ++) {
            scanf("%d", &a[i]);
            a[i] += 1;
            ans += getsum(N) - getsum(a[i]);
            add(a[i], 1);
        }


        int minn = ans;
        for(int i = 1; i <= N; i ++) {
            ans += N - a[i] + 1 - a[i];
            minn = min(minn, ans);
        }
        printf("%d\n", minn);
    }
    return 0;
}