Frane 收到了一项对一个数组进行排序的任务。该数组由 $N$ 个整数组成，每个整数都在 $1$ 到 $N$ 之间（含），且每个数在数组中恰好出现一次。Frane 想出了以下分为 $N$ 个阶段的排序算法，并将其命名为 turbosort：

• 在第一阶段，通过重复交换相邻元素，将数字 $1$ 移动到位置 $1$。
• 在第二阶段，以相同的方式将数字 $N$ 移动到位置 $N$。
• 在第三阶段，将数字 $2$ 移动到位置 $2$。
• 在第四阶段，将数字 $N-1$ 移动到位置 $N-1$。
• 依此类推。

换句话说，当阶段数为奇数时，Frane 会选择尚未选择的最小数字，并将其移动到其最终位置。在偶数阶段，他会选择尚未选择的最大数字。

编写一个程序，在给定初始数组的情况下，输出该算法每个阶段的交换次数。

输入格式

第一行包含一个整数 $N$（$1 \le N \le 100000$），表示数组中元素的数量。

接下来的 $N$ 行，每行包含一个介于 $1$ 到 $N$ 之间（含）的整数，表示待排序的数组。数组中不包含重复的元素。

输出格式

对于这 $N$ 个阶段中的每一个阶段，在单行中输出交换的次数。

子任务

在占总分 70% 的测试用例中，$N$ 将小于 100。

样例

输入样例 1

3
2
1
3

输出样例 1

1
0
0

输入样例 2

5
5
4
3
2
1

输出样例 2

4
3
2
1
0

输入样例 3

7
5
4
3
7
1
2
6

输出样例 3

4
2
3
0
2
1
0