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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import heapq\n\n\nclass DynamicMedian():\n    def __init__(self):\n        self.l_q = []  \n        self.r_q = []\n        self.l_sum = 0\n        self.r_sum = 0\n        \n    def add(self, val):\n        if len(self.l_q) == len(self.r_q):\n            self.l_sum += val\n            val = -heapq.heappushpop(self.l_q, -val)\n            self.l_sum -= val\n            heapq.heappush(self.r_q, val)\n            self.r_sum += val\n        else:\n            self.r_sum += val\n            val = heapq.heappushpop(self.r_q, val)\n            self.r_sum -= val\n            heapq.heappush(self.l_q, -val)\n            self.l_sum += val\n            \n    def median_low(self):\n        if len(self.l_q) + 1 == len(self.r_q):\n            return self.r_q[0]\n        else:\n            return -self.l_q[0]\n \n    def median_high(self):\n        return self.r_q[0]\n \n    def minimum_query(self):\n        res1 = (len(self.l_q) * self.median_high() - self.l_sum)\n        res2 = (self.r_sum - len(self.r_q) * self.median_high())\n        return res1 + res2\n\n#Binary Indexed Tree (Fenwick Tree)\nclass BIT():\n    def __init__(self, n):\n        self.n = n\n        self.bit = [0] * (n + 1)\n \n    def add(self, i, val):\n        i = i + 1\n        while i <= self.n:\n            self.bit[i] += val\n            i += i & -i\n \n    def _sum(self, i):\n        s = 0\n        while i > 0:\n            s += self.bit[i]\n            i -= i & -i\n        return s\n \n    def sum(self, i, j):\n        return self._sum(j) - self._sum(i)\n \n \nimport sys\ninput = sys.stdin.readline\n\nn = int(input())\na = list(map(int, input().split()))\nbit = BIT(n)\ndm = DynamicMedian()\n  \nmemo = {}\nfor i in range(n):\n    memo[a[i] - 1] = i\n\nb = [0] * n\nfor i in range(n):\n    dm.add(memo[i])\n    b[i] = dm.minimum_query() - (i+1)**2 // 4\n\nans = [0] * n\ntmp = 0\nfor i in range(len(a)):\n    bit.add(memo[i], 1)\n    tmp += bit.sum(memo[i] + 1, n)\n    ans[i] = tmp + b[i]\nprint(*ans)\n    \n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 19855