K Integers

题意翻译

给定 $n$ 和一个 $1$ 至 $n$ 这 $n$ 个数的排列 $p_1,p_2,p_3,\dots,p_n$ 。定义一次操作可以交换 $p$ 中相邻的两个数 $p_i,p_{i+1}$。定义函数 $f$ ，$f(k)$ 表示能使数列 $p$ 中存在连续子序列 $1,2,3,\dots,k$ 的最少操作次数。 求：$f(1),f(2),f(3),\dots,f(n)$ 的值

题目描述

You are given a permutation $ p_1, p_2, \ldots, p_n $ . In one move you can swap two adjacent values. You want to perform a minimum number of moves, such that in the end there will exist a subsegment $ 1,2,\ldots, k $ , in other words in the end there should be an integer $ i $ , $ 1 \leq i \leq n-k+1 $ such that $ p_i = 1, p_{i+1} = 2, \ldots, p_{i+k-1}=k $ . Let $ f(k) $ be the minimum number of moves that you need to make a subsegment with values $ 1,2,\ldots,k $ appear in the permutation. You need to find $ f(1), f(2), \ldots, f(n) $ .

输入输出格式

输入格式

The first line of input contains one integer $ n $ ( $ 1 \leq n \leq 200\,000 $ ): the number of elements in the permutation. The next line of input contains $ n $ integers $ p_1, p_2, \ldots, p_n $ : given permutation ( $ 1 \leq p_i \leq n $ ).

输出格式

Print $ n $ integers, the minimum number of moves that you need to make a subsegment with values $ 1,2,\ldots,k $ appear in the permutation, for $ 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