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

Source: codeforces | Difficulty: HARD
Tags: Sorting

Data structures


Solutions:
import sys
input = sys.stdin.buffer.readline

class bit:

	def __init__(self, n):
		self.n = n + 1
		self.mx_p = 0
		while 1 << self.mx_p < self.n:
			self.mx_p += 1
		self.a = [0] * self.n
		self.tot = 0

	def add(self, idx, val):
		self.tot += val
		idx += 1
		while idx < self.n:
			self.a[idx] += val
			idx += idx & -idx

	def sum_prefix(self, idx):
		tot = 0
		idx += 1
		while idx > 0:
			tot += self.a[idx]
			idx -= idx & -idx
		return tot

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

	def lower(self, val):
		if val > self.tot:
			return -1
		tot = 0
		idx = 0
		for i in range(self.mx_p, -1, -1):
			if idx + (1 << i) < self.n and tot + self.a[idx + (1 << i)] < val:
				tot += self.a[idx + (1 << i)]
				idx += 1 << i
		return idx
n = int(input())
p = list(map(int, input().split()))
p = sorted([[p[i], i] for i in range(n)])
ones = bit(n + 1)
ones_idx = bit(n + 1)
inversions = 0
for k in range(1, n + 1):
	(val, i) = p[k - 1]
	ones.add(i, 1)
	ones_idx.add(i, i)
	inversions += ones.sum(i + 1, n)
	num1l = (k + 1) // 2
	num1r = k - num1l
	idxl = ones.lower((k + 1) // 2)
	idxr = idxl + 1
	num0l = idxl + 1 - num1l
	num0r = n - idxr - num1r
	suml = ones_idx.sum_prefix(idxl)
	sumr = ones_idx.tot - suml
	movel = idxl * (idxl + 1) // 2 - suml - (num0l - 1) * num0l // 2
	mover = (n - 1 - idxr) * (n - 1 - idxr + 1) // 2 - (num1r * (n - 1) - sumr) - (num0r - 1) * num0r // 2
	print(inversions + movel + mover)


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


n = int(input())
arr = list(map(int, input().split()))
trees = [0] * (1 + n)
dic = [0] * (n + 1)
ans = [0] * n

def update(t, i, v):
	while i < len(t):
		t[i] += v
		i += lowbit(i)

def lowbit(x):
	return x & -x

def sum(t, i):
	ans = 0
	while i > 0:
		ans += t[i]
		i -= lowbit(i)
	return ans

def getmid(arr, l1, flag):
	(low, high) = (1, n)
	if l1 % 2 == 0 and flag:
		midv = l1 // 2
	else:
		midv = l1 // 2 + 1
	while low <= high:
		mid = (low + high) // 2
		ret = sum(arr, mid)
		if ret >= midv:
			high = mid - 1
		else:
			low = mid + 1
	return low
for i in range(n):
	dic[arr[i]] = i + 1
for i in range(1, n + 1):
	ans[i - 1] += sum(trees, n) - sum(trees, dic[i])
	if i >= 2:
		ans[i - 1] += ans[i - 2]
	update(trees, dic[i], 1)
visited = [0] * (1 + n)
mid = 0
last = 0
for i in range(1, n + 1):
	update(visited, dic[i], 1)
	mid = getmid(visited, i, dic[i] > mid)
	tt = sum(visited, dic[i])
	minus = min(tt - 1, i - tt)
	tmp = abs(dic[i] - mid - (tt - sum(visited, mid))) - minus
	ans[i - 1] += tmp + last
	last = tmp + last
print(' '.join(map(str, 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

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)


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


class Fenwick:

	def __init__(self, max_val):
		self.b = [0] * (max_val + 1)

	def update(self, i, increment):
		while i > 0 and i < len(self.b):
			self.b[i] += increment
			i += i & -i

	def sum(self, i):
		ans = 0
		while i > 0:
			ans += self.b[i]
			i -= i & -i
		return ans

	def at_sum(self, k):
		(a, b) = (0, len(self.b))
		while a < b:
			mid = (a + b) // 2
			if k <= self.sum(mid):
				b = mid
			else:
				a = mid + 1
		return a

def solve(p):
	pos = [0] * len(p)
	for (i, e) in enumerate(p):
		pos[e - 1] = i + 1
	ans = 0
	fenwick = Fenwick(len(p))
	for i in range(1, len(p) + 1):
		p = pos[i - 1]
		fenwick.update(p, 1)
		r = fenwick.sum(p)
		m = (i + 1) // 2
		if r <= m:
			m = m + (i % 2 == 0)
			ans += fenwick.at_sum(m) - p - m + 1 + i - r
		else:
			ans += p - fenwick.at_sum(m) + m - r
		yield ans
input()
a = [int(_) for _ in input().split()]
print(*solve(a))


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)