Time Limits: 1000 ms Memory Limits: 65536 KB

Description

你收到一项对数组进行排序的任务,数组中是1到N个一个排列。你突然想出以下一种特别的排序方法,分为以下N个阶段:
  •阶段1,把数字1通过每次交换相邻两个数移到位置1;
  •阶段2,用同样的方法把N移到位置N;
  •阶段3,把数字2移到位置2处;
  •阶段4,把数字N-1移到位置N-1处;
  •依此类推。
  换句话说,如果当前阶段为奇数,则把最小的未操作的数移到正确位置上,如果阶段为偶数,则把最大的未操作的数移到正确位置上。
  写一个程序,给出初始的排列情况,计算每一阶段交换的次数。

Input

第一行包含一个整数N(1<=N<=100000),表示数组中元素的个数。
  接下来N行每行一个整数描述初始的排列情况。

Output

输出每一阶段的交换次数。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
输入1:
3
2
1
3


输入2:
5
5
4
3
2
1

输出3:
7
5
4
3
7
1
2
6

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
输出1:
1
0
0

输出2:
4
3
2
1
0

输出3:
4
2
3
0
2
1
0

Data Constraint

Hint

【数据范围】
  70%的数据N<=100

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
#define MAX 100000
int n;
int numbers[MAX+1];
int position[MAX+1];
struct fenwick {
int a[MAX+1];
fenwick() {
memset( a, 0, sizeof a );
}
int query( int X ) {
int ret = 0;
for( int x = X; x > 0; x -= x&-x )
ret += a[x];
return ret;
}
int sum( int lo, int hi ) {
return query( hi ) - query( lo-1 );
}
void add( int X, int val ) {
for( int x = X; x <= n; x += x&-x )
a[x] += val;
}
} alive;
int main( void ) {
scanf( "%d", &n );
for( int i = 1; i <= n; ++i ) {
scanf( "%d", &numbers[i] );
position[numbers[i]] = i;
alive.add( i, 1 );
}
int mini = 1, maxi = n;

for( int i = 1; i <= n; ++i ) {
if( i%2 == 1 ) {
alive.add( position[mini], -1 );
printf( "%d\n", alive.sum( 1, position[mini] ) );
++mini;
} else {
alive.add( position[maxi], -1 );
printf( "%d\n", alive.sum( position[maxi], n ) );
--maxi;
}
}
return 0;
}