第 3 题冒泡冒泡 (`bubble`)

时间限制 1.0 s · 空间限制 256 MB · 75 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 bubble.in，输出文件 bubble.out。

KOI 2020 — 第 2 次选拔 (2차대회) 第 3 试

题目描述

给定 $N$ 个整数 $A_1, \dots, A_N$ ，用冒泡排序把它们排成单调不减（即不下降）的顺序。给定的整数之间可以有相同的值。冒泡排序只通过交换相邻两个数来完成排序，并且可以统计排序过程中相邻两数一共被交换了多少次。

例如给定三个数 3, 2, 1：第一轮交换两次相邻的数得到 2, 1, 3，第二轮交换 2 和 1 得到 1, 2, 3，一共需要 3 次交换。

现在考虑一个变体：在给定的 $N$ 个数中恰好把其中一个数换成另一个任意的数。初始的数都是整数，但换上去的新数可以是任意实数。换掉一个数之后，对 $N$ 个数做冒泡排序使其单调不减，希望交换次数最小。

显然，换哪一个数会影响所需的最小交换次数。例如在上面的例子 3, 2, 1 中，把最后一个数换成 4（实际上换成任何不小于 3 的数都行），只需交换一次 3 和 2，就得到升序的 2, 3, 4；而如果把第二个数 2 换掉，无论换成什么数都至少需要交换两次。

对每个 $i$ （ $1 \le i \le N$ ），请求出把 $A_i$ 换掉后冒泡排序所需的最小交换次数。

第一行给出 $N$ 。

第二行给出 $N$ 个待排序的数 $A_1, A_2, \dots, A_N$ ，中间用一个空格隔开。这些数都是整数。

输出一行，包含 $N$ 个数。其中第 $i$ 个数表示：当 $A_i$ 可以被换成任意实数时，把 $N$ 个数按单调不减次序冒泡排序所需的最小交换次数。

输入：

3
3 2 1

输出：

1 2 1

输入：

5
6 6 8 5 8

输出：

2 3 3 0 3