时空限制

1.5S/512M

题目描述

给定一个长度为 $n$ 的排列 $a$。

对于每个 $i \in [1, n]$，你需要独立地考虑以下操作：

1. 将元素 $a_i$ 从原排列中移出，剩余 $n-1$ 个元素保持相对顺序不变。
2. 将 $a_i$ 插入到这 $n-1$ 个元素形成的序列的任意位置（包括最前和最后），形成一个新的长度为 $n$ 的排列。

对于每个 $i$，你需要找到一个最佳的插入位置，使得新排列的逆序对数量最小。

请对每一个 $i$ 都输出这个最小的逆序对数量。

格式

输入格式

第一行包含一个整数 $n$，表示排列的长度。

第二行包含 $n$ 个用空格隔开的整数 $a_1, a_2, \ldots, a_n$，表示给定的排列。

输出格式

输出一行，包含 $n$ 个整数，用空格隔开。第 $i$ 个整数表示当移动原始排列中第 $i$ 个元素 $a_i$ 时，能够得到的最小逆序对数。

样例

样例输入 #1

5
1 2 5 4 3

样例输出 #1

3 3 1 2 1

数据规模

对于 $20\%$ 的数据，$2 \leq n \leq 100$。

对于 $50\%$ 的数据，$2 \leq n \leq 2000$。

对于 $100\%$ 的数据，$2 \leq n \leq 5 \times 10^5$，$a$ 是一个 $1$ 到 $n$ 的排列。