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 sys\nreader = (s.rstrip() for s in sys.stdin)\ninput = reader.__next__\n\nclass Binary_Indexed_Tree():\n    def __init__(self, n):\n        self.n = n\n        self.data = [0]*(n+1)\n\n    def add(self, i, x):\n        while i <= self.n:\n            self.data[i] += x\n            i += i & -i\n\n    def get(self, i):\n        return self.sum_range(i, i)\n\n    def sum(self, i):\n        ret = 0\n        while i:\n            ret += self.data[i]\n            i &= i-1\n        return ret\n\n    def sum_range(self, l, r):\n        return self.sum(r)-self.sum(l-1)\n\n    def lower_bound(self, w):\n        if w<=0:\n            return 0\n        i = 0\n        k = 1<<(self.n.bit_length())\n        while k:\n            if i+k <= self.n and self.data[i+k] < w:\n                w -= self.data[i+k]\n                i += k\n            k >>= 1\n        return i+1\n\nn = int(input())\na = list(map(int, input().split()))\nd = {j:i for i,j in enumerate(a)}\nBIT1 = Binary_Indexed_Tree(n)\nBIT2 = Binary_Indexed_Tree(n)\nBIT3 = Binary_Indexed_Tree(n)\n\ntentou = 0\nans = []\nfor i in range(n):\n    tmp = 0\n    p = d[i+1]\n    inv_p = n-p\n    tentou += BIT1.sum(inv_p)\n    BIT1.add(inv_p, 1)\n\n    BIT2.add(p+1, 1)\n    BIT3.add(p+1, p+1)\n    m = i//2+1\n    mean = BIT2.lower_bound(i//2+1)\n    tmp = 0\n    if i%2 == 0:\n        tmp -= m*(m-1)\n    else:\n        tmp -= m*m\n    tmp += tentou\n    left = BIT3.sum_range(1, mean)\n    right = BIT3.sum_range(mean, n)\n    if i%2 == 0:\n        left = mean*m - left\n        right = right - mean*m\n    else:\n        left = mean*m - left\n        right = right - mean*(m+1)\n    tmp += left + right\n    ans.append(tmp)\nprint(*ans)\n\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 18063