You are given a permutation p_1, p_2, …, 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,…, k, in other words in the end there should be an integer i, 1 ≤ i ≤ n-k+1 such that p_i = 1, p_{i+1} = 2, …, 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,…,k appear in the permutation.

You need to find f(1), f(2), …, f(n).

Input

The first line of input contains one integer n (1 ≤ n ≤ 200 000): the number of elements in the permutation.

The next line of input contains n integers p_1, p_2, …, p_n: given permutation (1 ≤ p_i ≤ n).

Output

Print n integers, the minimum number of moves that you need to make a subsegment with values 1,2,…,k appear in the permutation, for k=1, 2, …, 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: HARD
Tags: Sorting

Data structures
Skill types: Sorting

Data structures

Starter code:

Solutions:
n = int(input())
a = [0] + list(map(int, input().split()))
(pos, pb, ps) = [[0] * (n + 1) for x in range(3)]

def add(bit, i, val):
	while i <= n:
		bit[i] += val
		i += i & -i

def sum(bit, i):
	res = 0
	while i > 0:
		res += bit[i]
		i -= i & -i
	return res

def find(bit, sum):
	(i, t) = (0, 0)
	if sum == 0:
		return 0
	for k in range(17, -1, -1):
		i += 1 << k
		if i <= n and t + bit[i] < sum:
			t += bit[i]
		else:
			i -= 1 << k
	return i + 1
for i in range(1, n + 1):
	pos[a[i]] = i
invSum = 0
totalSum = 0
for i in range(1, n + 1):
	totalSum += pos[i]
	invSum += i - sum(pb, pos[i]) - 1
	add(pb, pos[i], 1)
	add(ps, pos[i], pos[i])
	mid = find(pb, i // 2)
	if i % 2 == 1:
		mid2 = find(pb, i // 2 + 1)
		seqSum = (i + 1) * (i // 2) // 2
	else:
		mid2 = mid
		seqSum = i * (i // 2) // 2
	leftSum = sum(ps, mid)
	rightSum = totalSum - sum(ps, mid2)
	print(rightSum - leftSum - seqSum + invSum, end=' ')


from bisect import bisect_right, bisect_left

class BITbisect:

	def __init__(self, InputProbNumbers):
		self.ind_to_co = [-10 ** 18]
		self.co_to_ind = {}
		for (ind, num) in enumerate(sorted(list(set(InputProbNumbers)))):
			self.ind_to_co.append(num)
			self.co_to_ind[num] = ind + 1
		self.max = len(self.co_to_ind)
		self.data = [0] * (self.max + 1)

	def __str__(self):
		retList = []
		for i in range(1, self.max + 1):
			x = self.ind_to_co[i]
			if self.count(x):
				c = self.count(x)
				for _ in range(c):
					retList.append(x)
		return '[' + ', '.join([str(a) for a in retList]) + ']'

	def __getitem__(self, key):
		key += 1
		s = 0
		ind = 0
		l = self.max.bit_length()
		for i in reversed(range(l)):
			if ind + (1 << i) <= self.max:
				if s + self.data[ind + (1 << i)] < key:
					s += self.data[ind + (1 << i)]
					ind += 1 << i
		if ind == self.max or key < 0:
			raise IndexError('BIT index out of range')
		return self.ind_to_co[ind + 1]

	def __len__(self):
		return self._query_sum(self.max)

	def __contains__(self, num):
		if not num in self.co_to_ind:
			return False
		return self.count(num) > 0

	def _query_sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

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

	def push(self, x):
		if not x in self.co_to_ind:
			raise KeyError('The pushing number didnt initialized')
		self._add(self.co_to_ind[x], 1)

	def delete(self, x):
		if not x in self.co_to_ind:
			raise KeyError('The deleting number didnt initialized')
		if self.count(x) <= 0:
			raise ValueError('The deleting number doesnt exist')
		self._add(self.co_to_ind[x], -1)

	def count(self, x):
		return self._query_sum(self.co_to_ind[x]) - self._query_sum(self.co_to_ind[x] - 1)

	def bisect_right(self, x):
		if x in self.co_to_ind:
			i = self.co_to_ind[x]
		else:
			i = bisect_right(self.ind_to_co, x) - 1
		return self._query_sum(i)

	def bisect_left(self, x):
		if x in self.co_to_ind:
			i = self.co_to_ind[x]
		else:
			i = bisect_left(self.ind_to_co, x)
		if i == 1:
			return 0
		return self._query_sum(i - 1)
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
Ind = [0] * (N + 1)
for (i, a) in enumerate(A):
	Ind[a] = i + 1
Bit = BITbisect(list(range(N + 1)))
ans = [0]
Bit.push(Ind[1])
a = 0
for n in range(2, N + 1):
	ind = Ind[n]
	f = Bit.bisect_left(ind)
	l = len(Bit)
	if l % 2 == 0:
		if f == l // 2:
			a += l // 2 - l // 2
		elif f < l // 2:
			p1 = Bit[l // 2 - 1]
			a += p1 - ind - 1 - (l // 2 - 1) + l - f
		else:
			p2 = Bit[l // 2]
			a += ind - p2 - 1 - (l // 2 - 1) + l - f
	else:
		p1 = Bit[l // 2]
		if f <= l // 2:
			a += p1 - ind - 1 - l // 2 + l - f
		else:
			a += ind - p1 - 1 - l // 2 + l - f
	ans.append(a)
	Bit.push(ind)
print(*ans, sep=' ')