1 #include<set> 2 #include<queue> 3 #include<ctime> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<iostream> 8 #include<algorithm> 9 using namespace std;10 const int N = 500010;11 #define Ch1 (T[i].s[0])12 #define Ch2 (T[i].s[1])13 #define For(i,n) for(int i=1;i<=n;i++)14 #define Rep(i,l,r) for(int i=l;i<=r;i++)15 16 void read(int &v){17     char ch=getchar();18     int num=0;19     while(ch>‘9‘||ch<‘0‘) ch=getchar();20     while(ch>=‘0‘&&ch<=‘9‘){21         num=num*10+ch-‘0‘;22         ch=getchar();23     }24     v=num;25 }26 27 struct treap{28     int v,size,pri;29     int s[2];30     void Sets(int x,int y){v=x;pri=y;size=1;}31 }T[N];32 33 int n,x,cnt,root;34 long long ans;35 36 void Update(int i){37     T[i].size=T[Ch1].size+T[Ch2].size+1;38 }39 40 void Rot(int &y,int f){41     int x=T[y].s[!f];42     T[y].s[!f]=T[x].s[f];43     T[x].s[f]=y;44     Update(y);Update(x);45     y=x;46 }47 48 void Insert(int &i,int x){49     if(!i){50         T[i=++cnt].Sets(x,rand());51         T[i].s[0]=T[i].s[1]=0;52         return;53     }54     int f=T[i].v>x;55     Insert(T[i].s[!f],x);56     if(T[T[i].s[!f]].pri>T[i].pri) Rot(i,f);57     else                           Update(i);    58 }59 60 int find(int i,int x){61     if(T[i].v==x) return T[Ch1].size+1;62     if(T[i].v<x) return T[Ch1].size+1+find(Ch2,x);63     if(T[i].v>x) return find(Ch1,x);64 }65 66 int main(){67     while(read(n),n){68         ans=0;69         cnt=root=0;70         For(i,n){71             read(x);72             Insert(root,x);     73             ans+=i-(find(root,x));         74         }75         cout<<ans<<endl;76     }77     return 0;78 }