线段树记录区间中已取走的个数
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100100
using namespace std;
int n;
int now;
long long ans;
int a[N],pos[N];
struct Tree{
int l,r,num;
}tree[N*3];
void build(int s,int t,int id){
tree[id].l=s,tree[id].r=t,tree[id].num=0;
if(s!=t){
int mid=(s+t)>>1;
build(s,mid,id<<1);
build(mid+1,t,id<<1|1);
}
}
void insert(int pos,int id){
tree[id].num++;
if(tree[id].l==tree[id].r)
return;
int mid=(tree[id].l+tree[id].r)>>1;
if(pos<=mid)insert(pos,id<<1);
else insert(pos,id<<1|1);
}
int query(int s,int t,int id){
if(tree[id].l==s && tree[id].r==t)
return tree[id].num;
int mid=(tree[id].l+tree[id].r)>>1;
if(mid>=t)return query(s,t,id<<1);
else if(mid<s)return query(s,t,id<<1|1);
else return query(s,mid,id<<1)+query(mid+1,t,id<<1|1);
}
int main(){
int i;
while(scanf("%d",&n)){
if(n==0)break;
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
pos[a[i]]=i;
}
ans=n;
ans+=min(pos[1]-1,n+1-pos[1]);
now=pos[1]; //now记录的是此时手中的球初始的位置,利用相对位置不变的性质,方便后面确定其他球的位置
build(1,n,1);
insert(pos[1],1); //这里pos[1]已经取走
for(i=2;i<=n;i++){
int tem;
if(pos[i]>now) tem=pos[i]-now-query(now,pos[i],1);
else tem=now-pos[i]+1-query(pos[i],now,1);
ans+=min(tem,n-i+1-tem);
now=pos[i];
insert(pos[i],1);
}
printf("%I64d\n",ans);
}
return 0;
}