最近，Grammy 在 Tony 的课上学习了三分搜索。当数组是单峰（unimodal）时，她可以使用该算法找到数组中的峰值。在这里，我们称一个数组 $a_1, a_2, \dots, a_n$ 是单峰的，当且仅当它满足以下条件之一：

• 存在一个下标 $k$ ($1 \le k \le n$)，使得 $a_1 < a_2 < \dots < a_k > a_{k+1} > \dots > a_n$。
• 存在一个下标 $k$ ($1 \le k \le n$)，使得 $a_1 > a_2 > \dots > a_k < a_{k+1} < \dots < a_n$。

作为 Grammy 的导师，Tony 想要考察 Grammy 是否完全理解了他在课堂上所教的内容，因此他留下了 $n$ 个任务让 Grammy 尝试进行三分搜索。任务如下：

最初，数组为空。每个任务都会在数组末尾追加一个不同的数字，Grammy 应该对该数组进行三分搜索。然而，由于 Tony 的粗心，数组在添加数字后可能不是单峰的。由于 Tony 已经去睡觉了，Grammy 必须自己解决这个问题。

对于每个任务，在 Grammy 尝试对其进行三分搜索之前，需要执行一些操作使其变为单峰。在每次操作中，Grammy 可以交换 $a_i$ 和 $a_{i+1}$ 的值（其中 $1 \le i < n$）。Grammy 是一个懒女孩，她认为如果她必须执行太多的操作，她宁愿等 Tony 醒来解决这个问题。对于每个任务，她想知道为了使数组变为单峰，她必须执行的最少操作次数是多少。你能帮帮她吗？

输入格式

输入包含单个测试用例。

第一行包含一个整数 $n$ ($1 \le n \le 200\,000$)，表示任务的数量。接下来的 $n$ 行中，第 $i$ 行包含一个整数 $a_i$ ($1 \le a_i \le 1\,000\,000\,000$)，表示在第 $i$ 个任务中追加的数字。

保证 $a_i$ 两两不同。

输出格式

输出包含 $n$ 行。每行包含一个整数，表示第 $i$ 个任务的答案。

样例

输入 1

9
11
4
5
14
1
9
19
8
10

输出 1

0
0
0
0
2
3
3
6
7