Description

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

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

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

Input Format

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

Output Format

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

3
2
1
3

1
0
0

5
5
4
3
2
1

4
3
2
1
0

Hint

数据规模与约定

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