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

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)
    
