[HOJ] 4 - 串珠珠問題

#include<stdio.h>
int s[100005],c[100005],loc[100005];
int main(){
    int n,i,j,x;
    long long int ans,all=0;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&x);
        s[i]=x,loc[x]=i+1;
    }
    for(i=n-1;i>=0;i--){
        for(j=s[i];j<=n;j+=j&-j)
            c[j]++;
        for(j=s[i]-1;j>0;j-=j&-j)
            all+=c[j];
    }
    ans=all;
    for(i=1;i<=n;i++){
        all+=n+1-2*loc[i];
        if(all<ans) ans=all;
    }
    printf("%lld\n",ans);
}