题目描述

Grammy 刚在 Tony 的算法课上学完三分搜索。Tony 告诉她：如果一个数组呈现单峰或单谷形态，那么就可以用类似的思想寻找极值。

这里称数组 $a_1,a_2,\ldots,a_n$ 是“峰谷数组”，当且仅当它满足下面两种条件之一：

• 存在一个下标 $k$，$1\le k\le n$，使得

• 存在一个下标 $k$，$1\le k\le n$，使得

为了检查 Grammy 是否真正理解了课堂内容，Tony 留下了 $n$ 次练习。最开始数组为空，第 $i$ 次练习会把一个新的、此前没有出现过的整数 $a_i$ 追加到数组右端，然后 Grammy 需要在当前数组上尝试三分搜索。

不过 Tony 写作业题时有些粗心：追加新数后，当前数组未必已经是峰谷数组。Grammy 不想等 Tony 睡醒后再问他，于是打算自己先把数组整理好。

在一次操作中，Grammy 可以选择某个 $i$，交换当前数组中相邻的两个数 $a_i$ 与 $a_{i+1}$。对于每一次练习，在真正开始三分搜索之前，她想知道至少需要多少次相邻交换，才能把当前数组变成一个峰谷数组。

请你帮她依次求出每次追加后的最少操作次数。

输入格式

输入只包含一组测试数据。

第一行包含一个整数 $n$，表示练习次数。

接下来 $n$ 行，第 $i$ 行包含一个整数 $a_i$，表示第 $i$ 次追加到数组右端的数。

保证所有 $a_i$ 两两不同。

输出格式

输出 $n$ 行，第 $i$ 行输出一个整数，表示第 $i$ 次追加后，将当前数组变成峰谷数组所需的最少相邻交换次数。

数据范围

• $1\le n\le 200000$；
• $1\le a_i\le 1000000000$；
• 所有 $a_i$ 两两不同。

样例 1

输入

9
11
4
5
14
1
9
19
8
10

输出

0
0
0
0
2
3
3
6
7