H-三维偏序_2023河南萌新联赛第（五）场：郑州轻工业大学

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一个由 $n$ 个正整数组成的序列 $a$ ，你可以通过 $j - i$ 个花费交换 $a_i, a_j\ (j > i)$ 两个元素。

我们定义一个位置 $i$ 是好的，当且仅当 $a_i$ 不与其他元素发生交换的前提下，使得 $a_1, \dots,a_{i -1} \le a_i$ ，即位置 $1 \sim i - 1$ 上的元素均小于等于 $a_i$ 。请注意，满足上述要求并不需要 $1 \sim i - 1$ 中元素有序，只需要满足与 $a_i$ 的相对大小关系即可。

对于所有的 $i \in \{1, 2 ,\dots,n\}$ ，分别求出使位置 $i$ 是好的所需要的最小花费是多少。如果怎么操作都无法使 $i$ 位置是好的，则输出 $-1$ 。

对于每个 $i$ ，进行的操作是相互独立的，并没有真正修改原数组的位置。

输入描述:

输入一行一个正整数 , 代表序列  的长度。

接下来一行  个正整数 ，代表序列  的元素。

输出描述:

输出一行  个整数，第  个整数代表使得  位置是好的所需要的最小花费，如果怎么操作都无法使  位置是好的，输出 。

示例1

输入

复制

7
1 9 1 9 8 1 0

输出

复制

0 0 4 0 7 -1 -1

说明

对于位置  ，左边并没有元素，因此不需要操作即可满足条件。

对于位置  ，左边有元素  ，由于 ， 因此不需要操作即可满足条件。

对于位置  ，左边有元素  ，由于 ， 不满足条件，此时我们可以花费  的代价，交换 ，此时满足条件。
注意，此时虽然交换了数组，但是由于不同位置的情况是独立的，尽管上一次交换了，在考虑下一个位置的情况时，我们仍然当  是原数组 。

对于位置 ，左边  均大于 ，但很明显，不论如何交换，不可能使得位置  上的元素均小于等于 ，因此输出 。