题目描述

给定一个长度为 $n$ 的 $1\sim n$ 的排列，你需要对其进行从小到大的排序，排序的规则如下：

• 第一个阶段，将数字 $1$ 通过与和它相邻的数字的交换来放置到 $1$ 号下标上。
• 第二个阶段，将数字 $n$ 进行如上同样的操作来放置到 $n$ 号下标上。
• 第三个阶段，将数字 $2$ 进行如上同样的操作来放置到 $2$ 号下标上。
• 第四个阶段，将数字 $n-1$ 进行如上同样的操作来放置到 $n-1$ 号下标上。

以此类推。

对于每一个阶段，输出交换的次数。

输入格式

输入第一行为一个整数 $n$。

接下来的 $n$ 行，每行一个整数。描述了一个 $1\sim n$ 的排列。

输出格式

输出共 $n$ 行，对于每个阶段，输出交换的次数。

3
2
1
3

1
0
0

5
5
4
3
2
1

4
3
2
1
0

7
5
4
3
7
1
2
6

4
2
3
0
2
1
0

提示

数据规模与约定

• 对于 $70\%$ 的数据，保证 $n<100$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 10^5$。

说明

题目译自 COCI2007-2008 CONTEST #2 T4 TURBO。