给你一个排列 $$$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