1 #include<cstdio>  2 #include<algorithm>  3 #include<vector>  4 using namespace std;  5 const int Nmax=10010;  6 const int INF=1e9;  7 int n,num[Nmax],hhash[Nmax],ans,lans;  8 vector<int> v;  9 struct Node 10 { 11     int l; 12     int r; 13     int data; 14 }; 15 Node tree[Nmax*4]; 16  17 void build(int root,int l,int r) 18 { 19     tree[root].l=l; 20     tree[root].r=r; 21     if(l==r) 22         return; 23     int ls=root<<1,rs=root<<1|1; 24     int mid=(l+r)>>1; 25     build(ls,l,mid); 26     build(rs,mid+1,r); 27 } 28  29 void init() 30 { 31     v.clear(); 32     for(int i=1;i<=n;i++) 33         hhash[i]=num[i]=0; 34     for(int i=0;i<n*4;i++) 35         tree[i].l=tree[i].r=tree[i].data=http://www.mamicode.com/0; 36     ans=0; 37     lans=INF; 38     build(1,1,n); 39 } 40  41 void push_up(int root) 42 { 43     tree[root].data=http://www.mamicode.com/tree[root<<1].data+tree[root<<1|1].data; 44 } 45  46 void update(int root,int l,int r,int data) 47 { 48     //printf("%d:%d,%d\n",root,tree[root].l,tree[root].r); 49     if(tree[root].l==l && tree[root].r==r) 50     { 51         tree[root].data=http://www.mamicode.com/data; 52         return; 53     } 54     int ls=root<<1,rs=root<<1|1,mid=(tree[root].l+tree[root].r)>>1; 55     if(mid>=r) 56         update(ls,l,r,data); 57     else if(mid<r) 58         update(rs,l,r,data); 59     else 60     { 61         update(ls,l,mid,data); 62         update(rs,mid+1,r,data); 63     } 64     push_up(root); 65 } 66  67 int query(int root,int l,int r) 68 { 69     if(tree[root].l>=l && tree[root].r <=r) 70         return tree[root].data; 71     int ls=root<<1,rs=root<<1|1,mid=(tree[root].l+tree[root].r)>>1; 72     if(mid>=r) 73         return query(ls,l,r); 74     else if(mid<l) 75         return query(rs,l,r); 76     else 77         return query(ls,l,mid)+query(rs,mid+1,r); 78 } 79  80 int main() 81 { 82     //freopen("hdu.in","r",stdin); 83     while(scanf("%d",&n)==1) 84     { 85         init(); 86         for(int i=1;i<=n;i++) 87         { 88             scanf("%d",&num[i]); 89             hhash[num[i]]=i; 90             v.push_back(num[i]); 91         } 92         sort(v.begin(),v.end()); 93         for(int i=0;i<v.size();i++) 94         { 95             //printf("%d\n",hhash[v[i]]); 96             update(1,hhash[v[i]],hhash[v[i]],1); 97             if(hhash[v[i]]!=n) 98                 ans+=query(1,hhash[v[i]]+1,n); 99         }100         for(int i=1;i<=n;i++)101         {102             ans=ans-num[i]+n-num[i]-1;103             if(ans<lans)104                 lans=ans;105         }106         printf("%d\n",lans);107     }108     return 0;109 }