BNUOJ 26228 Juggler

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <vector>
 8 #include <queue>
 9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #include <stack>
13 #define LL long long
14 #define INF 0x3f3f3f3f
15 using namespace std;
16 const int maxn = 100010;
17 LL d[maxn];
18 int pos[maxn],n;
19 int lowbit(int x){
20     return x&-x;
21 }
22 void add(int x,int val){
23     for(; x < maxn; x += lowbit(x)){
24         d[x] += val;
25     }
26 }
27 LL sum(int x){
28     LL temp = 0;
29     for(; x > 0; x -= lowbit(x))
30         temp += d[x];
31     return temp;
32 }
33 int main(){
34     int i,j,temp,cnt;
35     LL ans;
36     while(scanf("%d",&n),n){
37         memset(d,0,sizeof(d));
38         memset(pos,0,sizeof(pos));
39         for(i = 1; i <= n; i++){
40             scanf("%d",&temp);
41             pos[temp] = i;
42             add(i,1);
43         }
44         cnt = 1;
45         ans = 0;
46         for(i = 1; i <= n; i++){
47             ans++;
48             if(cnt != pos[i]){
49                 LL df = abs(sum(cnt-1)-sum(pos[i]-1));
50                 ans += min(df,n-i-df+1);
51             }
52             cnt = pos[i];
53             add(pos[i],-1);
54         }
55         printf("%I64d\n",ans);
56     }
57     return 0;
58 }