← 返回题目列表

Codeforces · 1268/C

C. K 整数

中文机器翻译题面 查看原题

给你一个排列 $$$p_1, p_2, \ldots, p_n$$$。

在一步操作中,您可以交换两个相邻的值。

你想要执行最少的移动次数,这样最后就会存在一个子段 $$$1,2,\ldots, k$$$,换句话说,最后应该有一个整数 $$$i$$$, $$$1 \leq i \leq n-k+1$$$ 使得 $$$p_i = 1, p_{i+1} = 2, \ldots, p_{i+k-1}=k$$$。

设 $$$f(k)$$$ 为在排列中出现值 $$$1,2,\ldots,k$$$ 的子分段所需的最小移动次数。

您需要找到 $$$f(1), f(2), \ldots, f(n)$$$。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 200\,000$$$):排列中的元素数量。

输入的下一行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$:给定排列 ($$$1 \leq p_i \leq n$$$)。

输出

打印 $$$n$$$ 整数,即在排列中出现值 $$$1,2,\ldots,k$$$ 的子段所需的最小移动次数,$$$k=1, 2, \ldots, n$$$。

示例

输入 #1

5
5 4 3 2 1

输出 #1

0 1 3 6 10

输入 #2

3
1 2 3

输出 #2

0 0 0