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


-----Input-----

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


-----Output-----

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


-----Examples-----
Input
5
5 4 3 2 1

Output
0 1 3 6 10 

Input
3
1 2 3

Output
0 0 0

Difficulty: competition

Starter code:

Solutions:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

class Binary_Indexed_Tree():
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)

    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def get(self, i):
        return self.sum_range(i, i)

    def sum(self, i):
        ret = 0
        while i:
            ret += self.data[i]
            i &= i-1
        return ret

    def sum_range(self, l, r):
        return self.sum(r)-self.sum(l-1)

    def lower_bound(self, w):
        if w<=0:
            return 0
        i = 0
        k = 1<<(self.n.bit_length())
        while k:
            if i+k <= self.n and self.data[i+k] < w:
                w -= self.data[i+k]
                i += k
            k >>= 1
        return i+1

n = int(input())
a = list(map(int, input().split()))
d = {j:i for i,j in enumerate(a)}
BIT1 = Binary_Indexed_Tree(n)
BIT2 = Binary_Indexed_Tree(n)
BIT3 = Binary_Indexed_Tree(n)

tentou = 0
ans = []
for i in range(n):
    tmp = 0
    p = d[i+1]
    inv_p = n-p
    tentou += BIT1.sum(inv_p)
    BIT1.add(inv_p, 1)

    BIT2.add(p+1, 1)
    BIT3.add(p+1, p+1)
    m = i//2+1
    mean = BIT2.lower_bound(i//2+1)
    tmp = 0
    if i%2 == 0:
        tmp -= m*(m-1)
    else:
        tmp -= m*m
    tmp += tentou
    left = BIT3.sum_range(1, mean)
    right = BIT3.sum_range(mean, n)
    if i%2 == 0:
        left = mean*m - left
        right = right - mean*m
    else:
        left = mean*m - left
        right = right - mean*(m+1)
    tmp += left + right
    ans.append(tmp)
print(*ans)



import heapq


class DynamicMedian():
    def __init__(self):
        self.l_q = []  
        self.r_q = []
        self.l_sum = 0
        self.r_sum = 0
        
    def add(self, val):
        if len(self.l_q) == len(self.r_q):
            self.l_sum += val
            val = -heapq.heappushpop(self.l_q, -val)
            self.l_sum -= val
            heapq.heappush(self.r_q, val)
            self.r_sum += val
        else:
            self.r_sum += val
            val = heapq.heappushpop(self.r_q, val)
            self.r_sum -= val
            heapq.heappush(self.l_q, -val)
            self.l_sum += val
            
    def median_low(self):
        if len(self.l_q) + 1 == len(self.r_q):
            return self.r_q[0]
        else:
            return -self.l_q[0]
 
    def median_high(self):
        return self.r_q[0]
 
    def minimum_query(self):
        res1 = (len(self.l_q) * self.median_high() - self.l_sum)
        res2 = (self.r_sum - len(self.r_q) * self.median_high())
        return res1 + res2

#Binary Indexed Tree (Fenwick Tree)
class BIT():
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)
 
    def add(self, i, val):
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i
 
    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
 
    def sum(self, i, j):
        return self._sum(j) - self._sum(i)
 
 
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
bit = BIT(n)
dm = DynamicMedian()
  
memo = {}
for i in range(n):
    memo[a[i] - 1] = i

b = [0] * n
for i in range(n):
    dm.add(memo[i])
    b[i] = dm.minimum_query() - (i+1)**2 // 4

ans = [0] * n
tmp = 0
for i in range(len(a)):
    bit.add(memo[i], 1)
    tmp += bit.sum(memo[i] + 1, n)
    ans[i] = tmp + b[i]
print(*ans)