Read problems statements in Mandarin Chinese and Russian. 

Sereja is hosting his birthday dinner. He invited his N close friends. Let us number the people from 1 to N according to the order in which they arrive at the event. The dinner is being held in long straight corridor in which people sit in a way such that they won't leave any empty space in between two consecutive persons at any given time. 

When a person number i arrives at the corridor, he must go and stand to the immediate right of the person numbered A[i] (if A[i] = 0, then this person just stands at the leftmost end of the line). 

But there is a problem, as there is no space between two consecutive persons at any given time, so for this person to sit, space must be created by moving either all the persons to left of the place to the left one step each, or all the persons to right of the place to the right one step each.  

Now, Sereja is wondering about what could be the minimum number of steps people will take so as to sit in the dinner party. Please find it fast, so that Sereja can peacefully entertain his guests.

------ Input ------ 

First line of input contain an integer T — the number of test cases. T tests follow.
First line of each test case contain the integer N, and the next line contains N integers — A[1], A[2], ... , A[N].

------ Output ------ 

For each test case, output a single line with the answer — the minimal number of steps required.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 100$
$0 ≤ A[i] < i$

----- Sample Input 1 ------ 
3
1
0
3
0 0 0
5
0 1 2 1 4
----- Sample Output 1 ------ 
0
0
3
----- explanation 1 ------ 

Example case 3. 

First three persons don't need any steps to sit. The line after the arrangement of these persons will look like [1, 2, 3].  
When person #4 comes in, he wants to sit to the right of person 1, so we need to either move the first person to the left, or the second and third persons to the right. The first case is clearly better. Now the line will look like [1, 4, 2, 3].  
When person #5 arrives, he will need to move 2 persons in either case. The final arrangement will be [1, 4, 5, 2, 3]. 

So total number of steps people moved during the entire process is 1 + 2 = 3. So the answer is 3.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Complete search

Constructive algorithms

Data structures

Ad-hoc


Solutions:
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	b = [0] * 2 * n
	si = n + 1
	ei = n + 1
	res = 0
	for (i, ai) in enumerate(a):
		if ai == 0:
			si -= 1
			b[si] = i + 1
		else:
			idx = b.index(ai)
			if b[idx + 1] == 0:
				b[idx + 1] = i + 1
				ei += 1
			else:
				left = idx - si + 1
				right = ei - idx - 1
				if left < right:
					res += left
					si -= 1
					for j in range(si, idx):
						b[j] = b[j + 1]
					b[idx] = i + 1
				else:
					res += right
					for j in range(ei, idx + 1, -1):
						b[j] = b[j - 1]
					ei += 1
					b[idx + 1] = i + 1
	print(res)


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	st = 0
	l = [1]
	for i in range(1, n):
		if lst[i] == 0:
			l.insert(0, i + 1)
		elif lst[i] in l:
			inx = l.index(lst[i])
			if inx + 1 > len(l) - inx - 1:
				st += len(l) - inx - 1
			else:
				st += inx + 1
			l.insert(inx + 1, i + 1)
		else:
			l.append(i + 1)
	print(st)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	p = []
	c = 0
	for j in range(1, n + 1):
		if a[j - 1] == 0:
			p.insert(0, j)
		else:
			l = p.index(a[j - 1]) + 1
			if l <= len(p) / 2:
				c += l
			else:
				c += len(p) - l
			p.insert(l, j)
	print(c)


T = int(input())
for _ in range(T):
	n = int(input())
	L = list(map(int, input().split()))
	M = []
	ans = 0
	for i in range(n):
		if L[i] == 0:
			M.insert(0, i + 1)
		else:
			a = L[i]
			b = M.index(a)
			m = len(M)
			ans += min(b + 1, m - b - 1)
			M.insert(b + 1, i + 1)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	place = []
	count = 0
	for k in range(1, n + 1):
		if a[k - 1] == 0:
			place.insert(0, k)
		else:
			loc = place.index(a[k - 1]) + 1
			if loc <= len(place) / 2:
				count += loc
			else:
				count += len(place) - loc
			place.insert(loc, k)
	print(count)


import sys
import math

def main(arr):
	ans = 0
	line = [None] * len(arr)
	line[0] = 1
	for i in range(1, len(arr)):
		e = i + 1
		next_to = arr[i]
		idx = -1
		if next_to != 0:
			for j in range(len(line)):
				if next_to == line[j]:
					idx = j
		left = 0
		right = 0
		for j in range(0, idx + 1):
			if line[j]:
				left += 1
		for j in range(idx + 1, len(line)):
			if line[j]:
				right += 1
		ans += min(right, left)
		line = line[0:idx + 1] + [e] + line[idx + 1:]
	return ans
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(main(arr))


import sys
import math

def main(arr):
	ans = 0
	line = []
	for i in range(len(arr)):
		e = i + 1
		idx = i
		if arr[i] != 0:
			idx = line.index(arr[i])
			line.insert(idx + 1, e)
		else:
			line.insert(0, e)
		ans += min(len(line[0:idx + 1]), len(line[idx + 2:]))
	return ans
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(main(arr))


T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	L = []
	Total = 0
	for i in range(1, N + 1):
		if A[i - 1] == 0:
			L.insert(0, i)
		else:
			ind = L.index(A[i - 1])
			L.insert(ind + 1, i)
			Total += min([len(L[:ind + 1]), len(L[ind + 2:])])
	print(Total)


try:
	for _ in range(int(input())):
		n = int(input())
		N = list(map(int, input().split()))
		seating = []
		swaps = 0
		for i in range(n):
			if N[i] == 0:
				seating.insert(0, i + 1)
			elif N[i] == seating[-1]:
				seating.append(i + 1)
			else:
				x = seating.index(N[i])
				seating.insert(x + 1, i + 1)
				swaps += min(x + 1, i - x - 1)
		print(swaps)
except EOFError:
	pass


for i in range(int(input())):
	n = int(input())
	people = list(map(int, input().split()))
	seating = [0]
	least_shift = 0
	for j in range(n):
		index = seating.index(people[j])
		least_shift += min(len(seating) - 1 - index, index)
		seating.insert(index + 1, j + 1)
	print(least_shift)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = []
	c = 0
	s.append(1)
	for k in range(1, n):
		if a[k] == 0:
			s.insert(0, k + 1)
		else:
			ind = s.index(a[k])
			s.insert(ind + 1, k + 1)
			if ind + 1 <= k - ind - 1:
				c += ind + 1
			else:
				c = c + k - ind - 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	a = [0]
	c = 0
	for i in range(n):
		p = a.index(arr[i])
		c += min(p, len(a) - 1 - p)
		a.insert(p + 1, i + 1)
	print(c)


for _ in range(int(input())):
	n = int(input())
	nog = list(map(int, input().split(' ')))
	count = 0
	npxy = [0]
	for i in range(n):
		pos = npxy.index(nog[i])
		count += min(pos, len(npxy) - pos - 1)
		npxy.insert(pos + 1, i + 1)
	print(count)


try:
	for t in range(int(input())):
		n = int(input())
		count = 0
		A = list(map(int, input().split()))
		B = [0]
		for i in range(n):
			pos = B.index(A[i])
			count += min(pos, len(B) - pos - 1)
			B.insert(pos + 1, i + 1)
		print(count)
except:
	pass


def getResult(n, arr):
	a = [0]
	c = 0
	for i in range(n):
		p = a.index(arr[i])
		c += min(p, len(a) - 1 - p)
		a.insert(p + 1, i + 1)
	return c
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(getResult(n, arr))


test_case = int(input())
while test_case > 0:
	steps = 0
	test_case -= 1
	n = int(input())
	array = list(map(int, input().split()))
	line = []
	for i in range(len(array)):
		if array[i] == 0:
			line.insert(0, i + 1)
		else:
			location = line.index(array[i])
			if location >= len(line) // 2:
				steps += len(line) - (location + 1)
				line.insert(location + 1, i + 1)
			else:
				steps += location + 1
				line.insert(location + 1, i + 1)
	print(steps)


T = int(input())
while T:
	n = int(input())
	li = [int(x) for x in input().split()]
	order = []
	steps = 0
	for i in range(len(li)):
		if li[i] == 0:
			order.insert(li[i], i + 1)
		else:
			len1 = len(order[:order.index(li[i])]) + 1
			len2 = len(order[order.index(li[i]) + 1:])
			steps += min([len1, len2])
			order.insert(order.index(li[i]) + 1, i + 1)
	print(steps)
	T -= 1


for tests in range(int(input())):
	N = int(input())
	A = [int(i) for i in input().split()]
	S = []
	i = 0
	moves = 0
	for j in range(N):
		i += 1
		new = A[j]
		if new == 0:
			S = [i] + S
		else:
			for k in range(len(S)):
				if new == S[k]:
					break
			k += 1
			moves += min(k, len(S) - k)
			S = S[:k] + [i] + S[k:]
	print(moves)


t = int(input())
for _ in range(t):
	n = int(input())
	b = list(map(int, input().split(' ')))
	count = 0
	a = []
	for i in range(n):
		c = b[i]
		if c == 0:
			if len(a) == 0:
				a.append(i + 1)
			else:
				a.insert(0, i + 1)
		elif c in a:
			ind = a.index(c)
			l = ind + 1
			r = len(a) - ind - 1
			count += min(l, r)
			a.insert(ind + 1, i + 1)
		else:
			a.append(i + 1)
	print(count)


def solve(arr, n):
	line = [1]
	total = 0
	for i in range(1, n):
		element = arr[i]
		if element == 0:
			line.insert(0, i + 1)
		else:
			index = line.index(arr[i])
			total += min(index + 1, len(line) - index - 1)
			line.insert(index + 1, i + 1)
	return total
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(arr, n))