A13147 | K Integers

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$ .