Given an array A[] which represents a Complete Binary Tree i.e, if index i is the parent, index 2*i + 1 is the left child and index 2*i + 2 is the right child.
The task is to find the minimum number of swaps required to convert it into a Binary Search Tree. 
Example 1:
Input:
A[] = { 5, 6, 7, 8, 9, 10, 11 }
Output: 3
Explanation: 
Binary tree of the given array:
Swap 1: Swap node 8 with node 5.
Swap 2: Swap node 9 with node 10.
Swap 3: Swap node 10 with node 7.
So, minimum 3 swaps are required.
Example 2:
Input: 
A[] = {1, 2, 3}
Output: 1
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minSwaps() which takes an array A[] and returns an integer as output.
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)
 
Constraints:
1 <= N <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD

Starter code: from typing import List





class Solution:

    def minSwaps(self, n : int, A : List[int]) -> int:

        # code here

        



Solutions:
from typing import List

class pair:

	def __init__(self, val, index):
		self.val = val
		self.index = index

	def __eq__(self, other):
		return self.val == other.val

	def __lt__(self, other):
		return self.val < other.val

class Solution:
	inorder = []

	def _inorder_traversal(self, n, arr, index):
		if index >= n:
			return
		self._inorder_traversal(n, arr, 2 * index + 1)
		self.inorder.append(arr[index])
		self._inorder_traversal(n, arr, 2 * index + 2)

	def minSwaps(self, n: int, A: List[int]) -> int:
		Solution.inorder = []
		self._inorder_traversal(n, A, 0)
		temp = []
		for index in range(n):
			temp.append(pair(Solution.inorder[index], index))
		temp.sort()
		visited = [-1] * n
		ans = 0
		for index in range(n):
			cycle_size = 0
			curr_index = index
			while visited[curr_index] == -1:
				cycle_size += 1
				visited[curr_index] = 1
				curr_index = temp[curr_index].index
			if cycle_size > 0:
				ans += cycle_size - 1
		return ans


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		arr = []

		def inorder(ind):
			if ind >= len(A):
				return
			inorder(2 * ind + 1)
			arr.append(A[ind])
			inorder(2 * ind + 2)
		inorder(0)
		sorted_ = sorted(arr)
		mapValToInd = dict()
		for i in range(len(sorted_)):
			val = sorted_[i]
			mapValToInd[val] = i
		swaps = 0
		for i in range(len(arr)):
			val = arr[i]
			while i != mapValToInd[val]:
				swaps += 1
				actualIndex = mapValToInd[val]
				temp = arr[actualIndex]
				arr[actualIndex] = val
				val = temp
		return swaps


from typing import List
import math

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:

		def inorder(a, n, index):
			if index >= n:
				return
			inorder(a, n, 2 * index + 1)
			v.append(a[index])
			inorder(a, n, 2 * index + 2)

		def _minSwaps():
			d = {}
			for i in range(n):
				d[v[i]] = i
			for i in range(n):
				v[i] = d[A[i]]
			i = ans = 0
			while i < n:
				if v[i] == i:
					i += 1
					continue
				ind = v[i]
				v[i] = v[ind]
				v[ind] = ind
				ans += 1
			return ans
		v = []
		inorder(A, n, 0)
		return _minSwaps()


from typing import List

class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

class Solution:

	def bst(self, arr, i, n):
		if i >= n or arr[i] is None:
			return None
		root = Node(arr[i])
		root.left = self.bst(arr, 2 * i + 1, n)
		root.right = self.bst(arr, 2 * i + 2, n)
		return root

	def inorder(self, root, arr):
		if root is None:
			return
		self.inorder(root.left, arr)
		arr.append(root.data)
		self.inorder(root.right, arr)

	def min_swaps_to_sort(self, arr):
		n = len(arr)
		elements = [(arr[i], i) for i in range(n)]
		elements.sort()
		visited = [False] * n
		min_swaps = 0
		for i in range(n):
			if visited[i] or elements[i][1] == i:
				continue
			cycle_size = 0
			cycle_min = elements[i][0]
			j = i
			while not visited[j]:
				visited[j] = True
				cycle_size += 1
				cycle_min = min(cycle_min, elements[j][0])
				j = elements[j][1]
			min_swaps += cycle_size - 1 + sum((1 for j in range(i, j + 1) if elements[j][0] < cycle_min))
		sorted_arr = [0] * n
		for i in range(n):
			sorted_arr[elements[i][1]] = elements[i][0]
		return min_swaps

	def minSwaps(self, n: int, A: List[int]) -> int:
		root = self.bst(A, 0, len(A))
		arr = []
		self.inorder(root, arr)
		ans = self.min_swaps_to_sort(arr)
		return ans


from typing import List
import collections

class TreeNode:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:

		def inorder(root):
			if not root:
				return
			inorder(root.left)
			res.append(root.data)
			inorder(root.right)
		q = collections.deque()
		root = TreeNode(A[0])
		q.append(root)
		j = 0
		while q:
			cur = q.popleft()
			if 2 * j + 1 < len(A):
				left = TreeNode(A[2 * j + 1])
				q.append(left)
				cur.left = left
			if 2 * j + 2 < len(A):
				right = TreeNode(A[2 * j + 2])
				q.append(right)
				cur.right = right
			j += 1
		res = []
		inorder(root)
		ans = 0
		A.sort()
		mp = {}
		for (ind, val) in enumerate(A):
			mp[val] = ind
		i = 0
		while i < len(A):
			if mp[res[i]] == i:
				i += 1
				continue
			else:
				ans += 1
				ind = mp[res[i]]
				(res[i], res[ind]) = (res[ind], res[i])
				i -= 1
				if i < 0:
					i = 0
		return ans


from typing import List

class Solution:

	def inorder(self, a, index, arr):
		if index >= len(a):
			return
		self.inorder(a, 2 * index + 1, arr)
		arr.append(a[index])
		self.inorder(a, 2 * index + 2, arr)

	def solver(self, arr):
		for i in range(len(arr)):
			arr[i] = (arr[i], i)
		arr.sort()
		count = 0
		(i, cnt) = (0, 0)
		while i < len(arr):
			j = arr[i][1]
			if j == i:
				i += 1
				continue
			(arr[i], arr[j]) = (arr[j], arr[i])
			cnt += 1
		return cnt

	def minSwaps(self, n: int, A: List[int]) -> int:
		arr = []
		self.inorder(A, 0, arr)
		return self.solver(arr)


from typing import List

class Solution:

	def minSwaps(self, n: int, num: List[int]) -> int:
		inorder = []

		def inord(i):
			if i >= len(num):
				return
			inord(2 * i + 1)
			inorder.append(num[i])
			inord(2 * i + 2)
		inord(0)
		actual = sorted(num)
		count = 0
		mp = dict()
		for i in range(n):
			if inorder[i] not in mp:
				mp[inorder[i]] = [i]
			else:
				mp[inorder[i]].append(i)
		for i in range(n):
			if actual[i] == inorder[i]:
				continue
			else:
				count += 1
				ind = mp[actual[i]].pop(0)
				(inorder[ind], inorder[i]) = (inorder[i], inorder[ind])
				mp[inorder[ind]].pop(0)
				mp[inorder[ind]].append(ind)
		return count


from typing import List

class Solution:

	def inorder(self, i, A, n, arr):
		if i >= n:
			return
		self.inorder(2 * i + 1, A, n, arr)
		arr.append(A[i])
		self.inorder(2 * i + 2, A, n, arr)

	def minSwaps(self, n: int, A: List[int]) -> int:
		arr = []
		self.inorder(0, A, n, arr)
		t = [[arr[i], i] for i in range(n)]
		t.sort()
		i = 0
		ans = 0
		while i < n:
			if t[i][1] == i:
				i += 1
				continue
			x = t[i][1]
			a = t[i][0]
			b = t[i][1]
			c = t[x][0]
			d = t[x][1]
			t[i][0] = c
			t[i][1] = d
			t[x][0] = a
			t[x][1] = b
			ans += 1
		return ans


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:

		def inorder(arr, temp, index, n):
			if index >= n:
				return
			inorder(arr, temp, 2 * index + 1, n)
			temp.append(arr[index])
			inorder(arr, temp, 2 * index + 2, n)
		temp = []
		inorder(A, temp, 0, len(A))
		c = 0
		for i in range(len(temp)):
			mini = temp[i]
			for j in range(i + 1, len(temp)):
				mini = min(mini, temp[j])
			if mini != temp[i]:
				ind = temp.index(mini)
				(temp[i], temp[ind]) = (temp[ind], temp[i])
				c += 1
		return c


from typing import List
from copy import deepcopy
from sys import setrecursionlimit
setrecursionlimit(10 ** 5 + 5)

class Solution:

	def loToIo(self, lord, iord, n, ind):
		left = 2 * ind + 1
		right = 2 * ind + 2
		if ind >= n:
			return iord
		iord = self.loToIo(lord, iord, n, left)
		iord.append(lord[ind])
		iord = self.loToIo(lord, iord, n, right)
		return iord

	def minSwaps(self, n: int, A: List[int]) -> int:
		iord = []
		iord = self.loToIo(A, iord, n, 0)
		temp = deepcopy(iord)
		d = {}
		temp.sort()
		for i in range(n):
			d[temp[i]] = i
		count = 0
		i = 0
		while i < n:
			if iord[i] == temp[i]:
				i += 1
			else:
				count += 1
				ind = d[iord[i]]
				(iord[i], iord[ind]) = (iord[ind], iord[i])
		return count


from typing import List

def inorder(idx, n, arr, ls):
	if idx >= n:
		return
	inorder(2 * idx + 1, n, arr, ls)
	ls.append(arr[idx])
	inorder(2 * idx + 2, n, arr, ls)

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		n = len(A)
		ls = []
		inorder(0, n, A, ls)
		swaps = 0
		dic = {}
		for i in range(n):
			dic[ls[i]] = i
		sortd = sorted(ls)
		for i in range(n):
			if ls[i] != sortd[i]:
				swaps += 1
				(a, b) = (ls[i], i)
				(c, d) = (sortd[i], dic[sortd[i]])
				(ls[b], ls[d]) = (ls[d], ls[b])
				dic[a] = d
				dic[c] = b
		return swaps


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:

		def inor(i=0, res=[]):
			if i >= n:
				return
			inor(2 * i + 1, res)
			res += (A[i],)
			inor(2 * i + 2, res)
			return res
		lst = [(x, i) for (i, x) in enumerate(inor())]
		lst.sort()
		res = i = 0
		while i < n:
			if lst[i][1] == i:
				i += 1
				continue
			res += 1
			j = lst[i][1]
			(lst[i], lst[j]) = (lst[j], lst[i])
		return res


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:

		def inor(i=0, res=[]):
			if i >= n:
				return
			inor(2 * i + 1, res)
			res += (A[i],)
			inor(2 * i + 2, res)
			return res
		lst = [(x, i) for (i, x) in enumerate(inor())]
		lst.sort()
		res = 0
		for i in range(n):
			while True:
				if lst[i][1] == i:
					break
				else:
					res += 1
					index = lst[i][1]
					(lst[i], lst[index]) = (lst[index], lst[i])
		return res


from typing import List

def inOrderTraversal(A, n, i):
	if i >= n:
		return []
	return inOrderTraversal(A, n, 2 * i + 1) + [A[i]] + inOrderTraversal(A, n, 2 * i + 2)

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		arr = inOrderTraversal(A, n, 0)
		sortedArr = sorted(arr)
		reqPos = {}
		for (i, x) in enumerate(sortedArr):
			reqPos[x] = i
		visit = {x: False for x in arr}
		swaps = 0
		for x in arr:
			cycleSize = 0
			curr = x
			while visit[curr] == False:
				visit[curr] = True
				curr = arr[reqPos[curr]]
				cycleSize += 1
			if cycleSize >= 2:
				swaps += cycleSize - 1
		return swaps


from typing import List

def inOrderTraversal(A, n, i):
	if i >= n:
		return []
	return inOrderTraversal(A, n, 2 * i + 1) + [A[i]] + inOrderTraversal(A, n, 2 * i + 2)

def merge(A, l, m, r):
	left = [A[i] for i in range(l, m + 1)]
	right = [A[i] for i in range(m + 1, r + 1)]
	(ln, rn) = (m - l + 1, r - m)
	swaps = 0
	(i, j) = (0, 0)
	while i < ln and j < rn:
		if left[i] <= right[j]:
			A[l + i + j] = left[i]
			i += 1
		else:
			swaps += ln - i
			A[l + i + j] = right[j]
			j += 1
	while i < ln:
		A[l + i + j] = left[i]
		i += 1
	while j < rn:
		A[l + i + j] = right[j]
		j += 1
	return swaps

def mergeSort(A, l, r):
	if l >= r:
		return 0
	m = (l + r) // 2
	p = mergeSort(A, l, m)
	q = mergeSort(A, m + 1, r)
	r = merge(A, l, m, r)
	return p + q + r

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		arr = inOrderTraversal(A, n, 0)
		sortedArr = sorted(arr)
		reqPos = {}
		for (i, x) in enumerate(sortedArr):
			reqPos[x] = i
		visit = {x: False for x in arr}
		swaps = 0
		for x in arr:
			cycleSize = 0
			curr = x
			while visit[curr] == False:
				visit[curr] = True
				curr = arr[reqPos[curr]]
				cycleSize += 1
			if cycleSize >= 2:
				swaps += cycleSize - 1
		return swaps


from typing import List

def inOrder(arr, n, idx, ls):
	if idx >= n:
		return
	inOrder(arr, n, 2 * idx + 1, ls)
	ls.append(arr[idx])
	inOrder(arr, n, 2 * idx + 2, ls)

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		n = len(A)
		v = []
		ans = 0
		inOrder(A, n, 0, v)
		B = sorted(v)
		dic = dict()
		for i in range(n):
			dic[v[i]] = i
		counti = 0
		for i in range(n):
			while B[i] != v[i]:
				counti += 1
				(a, b) = (v[i], i)
				(c, d) = (B[i], dic[B[i]])
				(v[b], v[d]) = (v[d], v[b])
				dic[a] = d
				dic[c] = b
		return counti


from typing import List
from collections import defaultdict

def findNumberOfCycles(arr1, arr2):
	ele_to_correct_pos_map = {}
	for i in range(len(arr1)):
		ele_to_correct_pos_map[arr1[i]] = i
	j_to_i_map = {}
	for j in range(len(arr2)):
		j_to_i_map[j] = ele_to_correct_pos_map[arr2[j]]
	cycles = 0
	mismatchSet = set(list(j_to_i_map.keys()))
	while mismatchSet:
		cycles += 1
		ele = mismatchSet.pop()
		while j_to_i_map[ele] in mismatchSet:
			mismatchSet.remove(j_to_i_map[ele])
			ele = j_to_i_map[ele]
	return cycles

class Solution:

	def __init__(self):
		self.inorder = []
		self.n = 0

	def doInorder(self, rooti, A):
		if rooti >= len(A):
			return
		self.doInorder(2 * rooti + 1, A)
		self.inorder.append(A[rooti])
		self.doInorder(2 * rooti + 2, A)

	def minSwaps(self, n: int, A: List[int]) -> int:
		self.inorder = []
		self.doInorder(0, A)
		correctInorder = sorted(self.inorder)
		cycles = findNumberOfCycles(correctInorder, self.inorder)
		return len(self.inorder) - cycles


from typing import List

class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

class Solution:

	def create(self, A):
		head = None
		n = head
		stack = []
		for i in range(len(A)):
			node = Node(A[i])
			if not head:
				head = node
				n = head
			else:
				if not n.left:
					n.left = node
				elif not n.right:
					n.right = node
					n = stack.pop(0)
				stack.append(node)
		return head

	def inorder(self, node):
		if not node:
			return
		self.inorder(node.left)
		ans.append(node.data)
		self.inorder(node.right)

	def swaps(self, arr, map1):
		vis = [False for i in range(len(arr))]
		swaps = 0
		for i in range(len(arr)):
			if vis[i]:
				continue
			else:
				n = map1[arr[i]]
				cycle = 0
				while not vis[n]:
					vis[n] = True
					cycle += 1
					n = map1[arr[n]]
				swaps += cycle - 1
		return swaps

	def minSwaps(self, n: int, A: List[int]) -> int:
		global ans
		ans = []
		root = self.create(A)
		self.inorder(root)
		A.sort()
		map1 = {}
		for i in range(len(A)):
			map1[A[i]] = i
		return self.swaps(ans, map1)


from typing import List

class Solution:

	def __init__(self):
		self.swaps = 0

	def inorder(self, A, n, ind, IOT):
		if ind >= n:
			return
		self.inorder(A, n, 2 * ind + 1, IOT)
		IOT.append(A[ind])
		self.inorder(A, n, ind * 2 + 2, IOT)

	def minSwaps(self, n: int, A: List[int]) -> int:
		IOT = []
		self.inorder(A, n, 0, IOT)
		swaps = 0
		index = {}
		for i in range(n):
			index[IOT[i]] = i
		B = sorted(A)
		for i in range(n):
			if index[B[i]] == i:
				continue
			else:
				(x, y) = (index[IOT[i]], index[B[i]])
				(index[IOT[i]], index[B[i]]) = (index[B[i]], index[IOT[i]])
				(IOT[x], IOT[y]) = (IOT[y], IOT[x])
				swaps += 1
		return swaps


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		inord = []

		def inorder(i):
			if i not in range(n):
				return
			inorder(2 * i + 1)
			inord.append(A[i])
			inorder(2 * i + 2)
		inorder(0)
		temp = sorted(inord)
		index = {}
		for i in range(n):
			index[inord[i]] = i
		ans = 0
		for i in range(n):
			if inord[i] != temp[i]:
				ans += 1
				init = inord[i]
				(inord[i], inord[index[temp[i]]]) = (inord[index[temp[i]]], inord[i])
				index[init] = index[temp[i]]
				index[temp[i]] = i
		return ans


from typing import List

class Solution:

	def inOrder(self, a, n, index, elements):
		if index >= n:
			return
		self.inOrder(a, n, 2 * index + 1, elements)
		elements.append(a[index])
		self.inOrder(a, n, 2 * index + 2, elements)

	def mergeLists(self, left, right, elements):
		n = len(left)
		m = len(right)
		i = 0
		j = 0
		k = 0
		while i < n and j < m:
			if left[i] < right[j]:
				elements[k] = left[i]
				i += 1
			else:
				elements[k] = right[j]
				j += 1
			k += 1
		while i < n:
			elements[k] = left[i]
			i += 1
			k += 1
		while j < m:
			elements[k] = right[j]
			j += 1
			k += 1

	def mergeSort(self, elements):
		if len(elements) <= 1:
			return
		mid = len(elements) // 2
		left = elements[:mid]
		right = elements[mid:]
		self.mergeSort(left)
		self.mergeSort(right)
		self.mergeLists(left, right, elements)

	def minSwaps(self, n: int, A: List[int]) -> int:
		unsorted = []
		self.inOrder(A, n, 0, unsorted)
		elements = []
		for i in range(len(unsorted)):
			elements.append(unsorted[i])
		self.mergeSort(elements)
		dic = {}
		nums = unsorted
		arr = elements
		for i in range(len(nums)):
			dic[nums[i]] = i
		c = 0
		for i in range(len(nums)):
			if arr[i] != nums[i]:
				c += 1
				index = dic[arr[i]]
				index2 = dic[nums[i]]
				dic[nums[i]] = index
				(nums[index], nums[index2]) = (nums[index2], nums[index])
		return c


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:

		def inorder(a, i, arr):
			if i <= 0 or i > n:
				return
			inorder(a, i * 2, arr)
			arr.append(a[i - 1])
			inorder(a, i * 2 + 1, arr)

		def find_min(arr):
			ans = 0
			for i in range(len(arr)):
				if arr[i][0] == i:
					continue
				j = i
				swap = 0
				while j != arr[j][0]:
					ind = arr[j][0]
					(arr[j], arr[ind]) = (arr[ind], arr[j])
					swap += 1
				ans += swap
			return ans
		arr = []
		inorder(A, 1, arr)
		arr_enum = list(enumerate(arr))
		arr_enum.sort(key=lambda _: _[1])
		return find_min(arr_enum)


from typing import List
from copy import deepcopy

class Solution:

	def loToPo(self, lord, pord, n, ind):
		left = 2 * ind + 1
		right = 2 * ind + 2
		if ind >= n:
			return pord
		pord = self.loToPo(lord, pord, n, left)
		pord.append(lord[ind])
		pord = self.loToPo(lord, pord, n, right)
		return pord

	def minSwaps(self, n: int, A: List[int]) -> int:
		pord = []
		pord = self.loToPo(A, pord, n, 0)
		temp = deepcopy(pord)
		d = {}
		temp.sort()
		for i in range(n):
			d[temp[i]] = i
		count = 0
		i = 0
		while i < n:
			if pord[i] == temp[i]:
				i += 1
			else:
				count += 1
				ind = d[pord[i]]
				(pord[i], pord[ind]) = (pord[ind], pord[i])
		return count


from typing import List

class Solution:

	def inorder(self, a, n, index, v):
		if index >= n:
			return
		self.inorder(a, n, 2 * index + 1, v)
		v.append(a[index])
		self.inorder(a, n, 2 * index + 2, v)

	def minSwaps(self, n: int, A: List[int]) -> int:
		v = []
		self.inorder(A, n, 0, v)
		B = sorted(v)
		dic = dict()
		for i in range(n):
			dic[v[i]] = i
		counti = 0
		for i in range(n):
			while B[i] != v[i]:
				counti += 1
				(a, b) = (v[i], i)
				(c, d) = (B[i], dic[B[i]])
				(v[b], v[d]) = (v[d], v[b])
				dic[a] = d
				dic[c] = b
		return counti


from typing import List

class Solution:

	def inorder_traversal(self, A, n, idx, inorder):
		if idx >= n:
			return
		self.inorder_traversal(A, n, 2 * idx + 1, inorder)
		inorder.append(A[idx])
		self.inorder_traversal(A, n, 2 * idx + 2, inorder)

	def minSwaps(self, n: int, A: List[int]) -> int:
		inorder = []
		self.inorder_traversal(A, n, 0, inorder)
		arr_pos = [(inorder[i], i) for i in range(n)]
		arr_pos.sort()
		visited = [False] * n
		count = 0
		for i in range(n):
			if visited[i] or arr_pos[i][1] == i:
				continue
			j = arr_pos[i][1]
			cycle_size = 0
			while not visited[j]:
				visited[j] = True
				j = arr_pos[j][1]
				cycle_size += 1
			count += cycle_size - 1
		return count


from typing import List
from collections import deque

class Node:

	def __init__(self, val):
		self.val = val
		self.left = None
		self.right = None

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		root = Node(A[0])
		tree = deque([[root, 0]])
		while tree:
			(node, index) = tree.popleft()
			left = 2 * index + 1
			right = 2 * index + 2
			if left < n:
				l = Node(A[left])
				tree.append([l, left])
				node.left = l
			if right < n:
				r = Node(A[right])
				tree.append([r, right])
				node.right = r

		def inorder(root):
			if not root:
				return
			inorder(root.left)
			arr.append(root.val)
			inorder(root.right)
		arr = []
		inorder(root)
		dict = {}
		for i in range(len(arr)):
			dict[arr[i]] = i
		final = sorted(arr)
		swap = 0
		i = 0
		for i in range(n):
			while final[i] != arr[i]:
				index = dict[final[i]]
				(final[index], final[i]) = (final[i], final[index])
				swap += 1
		return swap


from typing import List

class Solution:

	def __init__(self):
		self.v = []
		self.t = []

	def inorder(self, a, n, index):
		if index >= n:
			return
		self.inorder(a, n, 2 * index + 1)
		self.v.append(a[index])
		self.inorder(a, n, 2 * index + 2)

	def minSwaps(self, n: int, A: List[int]) -> int:
		self.inorder(A, n, 0)
		t = [[self.v[i], i] for i in range(n)]
		ans = i = 0
		t.sort()
		while i < n:
			if i == t[i][1]:
				i += 1
				continue
			else:
				pos = t[i][1]
				(t[i], t[pos]) = (t[pos], t[i])
				ans += 1
		return ans


from typing import List

def inorder_(A, index):
	global inorder
	if index >= len(A):
		return
	inorder_(A, 2 * index + 1)
	inorder.append(A[index])
	inorder_(A, 2 * index + 2)
	return inorder

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		global inorder
		inorder = []
		inorder_(A, 0)
		l = []
		for i in range(len(inorder)):
			l.append([inorder[i], i])
		l.sort()
		sol = []
		for i in range(len(inorder)):
			sol.append(l[i][1])
		swap = 0
		k = 0
		while k < len(inorder):
			if sol[k] == k:
				k += 1
			else:
				swap += 1
				temp = sol[k]
				sol[k] = sol[sol[k]]
				sol[temp] = temp
		return swap


from typing import List

def ino(data, root, n):
	if root >= n:
		return []
	ele = []
	ele += ino(data, 2 * root + 1, n)
	ele += [data[root]]
	ele += ino(data, 2 * root + 2, n)
	return ele

class Solution:

	def minSwaps(self, n: int, arr: List[int]) -> int:
		ele = ino(arr, 0, n)
		temp = sorted(ele)
		hm = {}
		for i in range(n):
			hm[ele[i]] = i
		c = 0
		for i in range(n):
			if ele[i] == temp[i]:
				continue
			c += 1
			nidx = hm[temp[i]]
			hm[ele[i]] = nidx
			hm[ele[nidx]] = i
			(ele[i], ele[nidx]) = (ele[nidx], ele[i])
		return c


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		arr = []

		def inorder(A, n, index):
			nonlocal arr
			if index >= n:
				return
			inorder(A, n, 2 * index + 1)
			arr.append(A[index])
			inorder(A, n, 2 * index + 2)
		inorder(A, n, 0)
		ans = self.help(arr)
		return ans

	def help(self, nums):
		arr = sorted(nums)
		dic = {}
		for i in range(len(nums)):
			dic[nums[i]] = i
		count = 0
		for i in range(len(nums)):
			if arr[i] != nums[i]:
				count += 1
				index = dic[arr[i]]
				index2 = dic[nums[i]]
				dic[arr[i]] = index2
				dic[nums[i]] = index
				(nums[index2], nums[index]) = (nums[index], nums[index2])
		return count


from typing import List
from collections import deque

class Node:

	def __init__(self, val):
		self.val = val
		self.left = None
		self.right = None

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		root = Node(A[0])
		tra_q = deque([[root, 0]])
		while tra_q:
			(node, index) = tra_q.popleft()
			left_i = 2 * index + 1
			right_i = 2 * index + 2
			if left_i < n:
				l = Node(A[left_i])
				tra_q.append([l, left_i])
				node.left = l
			if right_i < n:
				r = Node(A[right_i])
				tra_q.append([r, right_i])
				node.right = r
		ino = []

		def inorder(root):
			if root:
				inorder(root.left)
				ino.append(root.val)
				inorder(root.right)
		inorder(root)
		swaps = 0
		d = {}
		for i in range(len(ino)):
			d[ino[i]] = i
		final = sorted(ino)
		i = 0
		while i < len(ino):
			if ino[i] == final[i]:
				i += 1
			else:
				ind = d[final[i]]
				d[ino[ind]] = i
				d[ino[i]] = ind
				(ino[ind], ino[i]) = (ino[i], ino[ind])
				i += 1
				swaps += 1
		return swaps


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		lo = self.lot(0, n, A)
		sor = sorted(lo)
		edges = {}
		vis = {}
		ans = 0
		for i in range(n):
			edges[sor[i]] = lo[i]
		for start in range(n):
			if vis.get(sor[start]) is not None:
				continue
			else:
				count = 0
				cur = sor[start]
				while vis.get(cur) is None:
					vis[cur] = True
					cur = edges[cur]
					count += 1
				ans += count - 1
		return ans

	def lot(self, index, n, A):
		if index > n - 1:
			return []
		else:
			return self.lot(2 * index + 1, n, A) + [A[index]] + self.lot(2 * index + 2, n, A)


from typing import List

class Node:

	def __init__(self, data, left=None, right=None):
		self.val = data
		self.left = left
		self.right = right

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:

		def util(i):
			if i >= n:
				return None
			root = Node(A[i])
			root.left = util(2 * i + 1)
			root.right = util(2 * i + 2)
			return root
		root = util(0)

		def inorder(root):
			if not root:
				return
			inorder(root.left)
			arr.append(root.val)
			inorder(root.right)
		arr = []
		inorder(root)
		temp = [[arr[i], i] for i in range(n)]
		temp.sort(key=lambda x: x[0])
		count = 0
		i = 0
		while i < n:
			if temp[i][1] != i:
				count += 1
				(temp[temp[i][1]], temp[i]) = (temp[i], temp[temp[i][1]])
			else:
				i += 1
		return count


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:

		def swap(i, j, temp):
			tmp = temp[i]
			temp[i] = temp[j]
			temp[j] = tmp
		self.arr = []

		def inorder(i):
			if i >= n:
				return
			inorder(2 * i + 1)
			self.arr.append(A[i])
			inorder(2 * i + 2)
		inorder(0)
		temp = []
		for (i, v) in enumerate(self.arr):
			temp.append([v, i])
		temp.sort(key=lambda x: x[0])
		count = 0
		i = 0
		while i < n:
			if temp[i][1] != i:
				count += 1
				swap(temp[i][1], i, temp)
				i -= 1
			i += 1
		return count


from typing import List

class Solution:
	global a
	a = []

	def inorder(self, arr, i, n):
		a = []
		if i >= n:
			return []
		a += self.inorder(arr, 2 * i + 1, n)
		a += [arr[i]]
		a += self.inorder(arr, 2 * i + 2, n)
		return a

	def minSwaps(self, n: int, A: List[int]) -> int:
		global a
		nums = self.inorder(A, 0, n)
		srt = sorted(A)
		d = dict()
		for i in range(n):
			d[srt[i]] = i
		ans = 0
		i = 0
		while i < n:
			if d[nums[i]] != i:
				t = d[nums[i]]
				(nums[i], nums[t]) = (nums[t], nums[i])
				ans += 1
			else:
				i += 1
		return ans


from typing import List

class Solution:

	def minSwaps(self, n: int, arr: List[int]) -> int:
		global inor
		nums = inord(arr, 0, n)
		srt = sorted(arr)
		mapx = dict()
		for i in range(n):
			mapx[srt[i]] = i
		ans = 0
		i = 0
		while i < n:
			if mapx[nums[i]] != i:
				idx = mapx[nums[i]]
				(nums[i], nums[idx]) = (nums[idx], nums[i])
				ans += 1
			else:
				i += 1
		return ans

def inord(arr, i, n):
	if i >= n:
		return []
	inor = []
	inor += inord(arr, 2 * i + 1, n)
	inor += [arr[i]]
	inor += inord(arr, 2 * i + 2, n)
	return inor


from typing import List

class Solution:

	def get_array(self, arr, n, index):
		if index >= n:
			return []
		(left, right) = (self.get_array(arr, n, 2 * index + 1), self.get_array(arr, n, 2 * index + 2))
		return [*left, arr[index], *right]

	def minSwaps(self, n: int, A: List[int]) -> int:
		arr = self.get_array(A, n, 0)
		ans = sorted(arr)
		dic = {}
		for (index, num) in enumerate(ans):
			dic[num] = index
		num_swaps = 0
		for (index, num) in enumerate(arr):
			indi = index
			curr_swaps = 0
			while ans[indi] != arr[indi]:
				temp = arr[indi]
				arr[indi] = ans[indi]
				indi = dic[temp]
				curr_swaps += 1
			num_swaps += max(0, curr_swaps - 1)
		return num_swaps


from typing import List

class Solution:

	def minSwaps(self, n: int, z: List[int]) -> int:
		x = []

		def f(i):
			if i >= n:
				return
			f(2 * i + 1)
			x.append(z[i])
			f(2 * i + 2)
		f(0)
		y = sorted(x)
		ind = {}
		for i in range(n):
			ind[y[i]] = i
		v = [0 for i in range(n)]
		ans = 0
		for i in range(n):
			if v[i] == 0:
				c = 0
				while v[i] == 0:
					v[i] = 1
					i = ind[x[i]]
					c += 1
				ans += c - 1
		return ans


from typing import List

class Solution:

	def inorder(self, A, n, i, ans):
		if i >= n:
			return
		self.inorder(A, n, 2 * i + 1, ans)
		ans.append(A[i])
		self.inorder(A, n, 2 * i + 2, ans)

	def minSwaps(self, n: int, A: List[int]) -> int:
		arr = []
		self.inorder(A, n, 0, arr)
		hm = {}
		tmp = sorted([c for c in arr])
		for i in range(n):
			hm[arr[i]] = i
		ans = 0
		i = 0
		while i < n:
			if arr[i] != tmp[i]:
				ans += 1
				pos = hm[tmp[i]]
				tt = tmp[pos]
				tmp[pos] = tmp[i]
				tmp[i] = tt
			else:
				i += 1
		return ans


from typing import List

class Solution:

	def getInorder(self, t, n, i, inorder=[]):
		if i >= n:
			return
		leftInd = 2 * i + 1
		rightInd = 2 * i + 2
		self.getInorder(t, n, leftInd, inorder)
		inorder.append(t[i])
		self.getInorder(t, n, rightInd, inorder)

	def minSwaps(self, n: int, A: List[int]) -> int:
		inorder = []
		self.getInorder(A, n, 0, inorder)
		sortedInorder = sorted(inorder)
		valToIndex = {}
		for i in range(n):
			valToIndex[sortedInorder[i]] = i
		i = 0
		minSwaps = 0
		while i < n:
			currEle = inorder[i]
			supposedIndex = valToIndex[currEle]
			if i == supposedIndex:
				i += 1
			else:
				minSwaps += 1
				(inorder[i], inorder[supposedIndex]) = (inorder[supposedIndex], inorder[i])
		return minSwaps


from typing import List

class Solution:

	def inorder(self, a, res, index):
		if index < n:
			self.inorder(a, res, 2 * index + 1)
			res.append(a[index])
			self.inorder(a, res, 2 * index + 2)

	def minSwaps(self, n: int, A: List[int]) -> int:
		a = A
		res = []
		self.inorder(a, res, 0)
		m = {}
		b = res.copy()
		b.sort()
		a = res.copy()
		for i in range(n):
			m[b[i]] = i
		for i in range(n):
			a[i] = m[a[i]]
		i = 0
		c = 0
		while i < n:
			if a[i] == i:
				i += 1
			else:
				x = a[i]
				(a[x], a[i]) = (a[i], a[x])
				c += 1
		return c


from typing import List

class node:

	def __init__(self, data):
		self.left = None
		self.right = None
		self.data = data

class Solution:

	def __init__(self):
		self.one = []
		self.two = []
		self.hash = {}
		self.count = 0

	def complete(self, root, A, n, i):
		if i < n:
			temp = node(A[i])
			root = temp
			root.left = self.complete(root.left, A, n, 2 * i + 1)
			root.right = self.complete(root.right, A, n, 2 * i + 2)
		return root

	def trav(self, temp):
		if temp is None:
			return None
		self.trav(temp.left)
		self.two.append(temp.data)
		self.trav(temp.right)

	def minSwaps(self, n: int, A: List[int]) -> int:
		root = None
		root = self.complete(root, A, n, 0)
		self.trav(root)
		self.one = self.two.copy()
		self.two.sort()
		for i in range(len(self.one)):
			if self.one[i] != self.two[i]:
				self.count += 1
				k = self.one.index(self.two[i])
				(self.one[i], self.one[k]) = (self.one[k], self.one[i])
		return self.count

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		A = IntArray().Input(n)
		obj = Solution()
		res = obj.minSwaps(n, A)
		print(res)


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		inorder = []
		self.find_inorder(A, inorder)
		ans = self.minimum_swaps(inorder)
		return ans

	def find_inorder(self, array, inorder, index=0):
		if index >= len(array):
			return
		self.find_inorder(array, inorder, 2 * index + 1)
		inorder.append(array[index])
		self.find_inorder(array, inorder, 2 * index + 2)

	def minimum_swaps(self, array):
		if len(array) == 0:
			return 0
		vector = []
		for i in range(len(array)):
			vector.append([array[i], i])
		vector.sort()
		i = 0
		min_swaps = 0
		while i < len(vector):
			if i != vector[i][1]:
				min_swaps += 1
				to_swap_with = vector[i][1]
				(vector[i], vector[to_swap_with]) = (vector[to_swap_with], vector[i])
			else:
				i += 1
		return min_swaps

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		A = IntArray().Input(n)
		obj = Solution()
		res = obj.minSwaps(n, A)
		print(res)


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		a = []

		def ino(A, a, i, n):
			if i >= n:
				return
			ino(A, a, 2 * i + 1, n)
			a.append(A[i])
			ino(A, a, 2 * i + 2, n)
		ino(A, a, 0, n)
		dict = {}
		for i in range(0, n):
			dict[a[i]] = i
		swaps = 0
		i = 0
		j = 0
		while i < n and j < n:
			if a[i] == A[i]:
				i += 1
				j += 1
			else:
				temp1 = dict[A[i]]
				temp2 = a[i]
				(a[dict[A[i]]], a[i]) = (a[i], a[dict[A[i]]])
				dict[a[i]] = i
				dict[temp2] = temp1
				swaps += 1
				i += 1
				j += 1
		return swaps

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		A = IntArray().Input(n)
		obj = Solution()
		res = obj.minSwaps(n, A)
		print(res)


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		self.res = []

		def magic(i):
			if i >= len(A):
				return
			magic(2 * i + 1)
			self.res.append(A[i])
			magic(2 * i + 2)
		magic(0)
		arr = [*enumerate(self.res)]
		arr.sort(key=lambda x: x[1])
		seen = set()
		N = len(A)
		res = 0
		for i in range(N):
			if i in seen or arr[i][0] == i:
				continue
			j = i
			cycle = 0
			while j not in seen:
				seen.add(j)
				j = arr[j][0]
				cycle += 1
			if cycle > 1:
				res += cycle - 1
		return res

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		A = IntArray().Input(n)
		obj = Solution()
		res = obj.minSwaps(n, A)
		print(res)


from typing import List

class Solution:

	def inOrder(self, a, n, index, elements):
		if index >= n:
			return
		self.inOrder(a, n, 2 * index + 1, elements)
		elements.append(a[index])
		self.inOrder(a, n, 2 * index + 2, elements)

	def mergeLists(self, left, right, elements):
		n = len(left)
		m = len(right)
		i = 0
		j = 0
		k = 0
		while i < n and j < m:
			if left[i] < right[j]:
				elements[k] = left[i]
				i += 1
			else:
				elements[k] = right[j]
				j += 1
			k += 1
		while i < n:
			elements[k] = left[i]
			i += 1
			k += 1
		while j < m:
			elements[k] = right[j]
			j += 1
			k += 1

	def mergeSort(self, elements):
		if len(elements) <= 1:
			return
		mid = len(elements) // 2
		left = elements[:mid]
		right = elements[mid:]
		self.mergeSort(left)
		self.mergeSort(right)
		self.mergeLists(left, right, elements)

	def Cloning(self, li1):
		li_copy = li1
		return li_copy

	def minSwaps(self, n: int, A: List[int]) -> int:
		unsorted = []
		self.inOrder(A, n, 0, unsorted)
		elements = []
		for i in range(len(unsorted)):
			elements.append(unsorted[i])
		self.mergeSort(elements)
		dic = {}
		nums = unsorted
		arr = elements
		for i in range(len(nums)):
			dic[nums[i]] = i
		c = 0
		for i in range(len(nums)):
			if arr[i] != nums[i]:
				c += 1
				index = dic[arr[i]]
				index2 = dic[nums[i]]
				dic[arr[i]] = index2
				dic[nums[i]] = index
				(nums[index], nums[index2]) = (nums[index2], nums[index])
		return c

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		A = IntArray().Input(n)
		obj = Solution()
		res = obj.minSwaps(n, A)
		print(res)


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		v = []
		self.inorder(n, A, 0, v)
		arr = v
		ans = 0
		temp = arr.copy()
		h = {}
		temp.sort()
		for i in range(n):
			h[arr[i]] = i
		init = 0
		for i in range(n):
			if arr[i] != temp[i]:
				ans += 1
				init = arr[i]
				(arr[i], arr[h[temp[i]]]) = (arr[h[temp[i]]], arr[i])
				h[init] = h[temp[i]]
				h[temp[i]] = i
		return ans

	def inorder(self, n, A: List[int], index: int, v: List[int]) -> List[int]:
		if index >= n:
			return
		self.inorder(n, A, 2 * index + 1, v)
		v.append(A[index])
		self.inorder(n, A, 2 * index + 2, v)

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		A = IntArray().Input(n)
		obj = Solution()
		res = obj.minSwaps(n, A)
		print(res)


from typing import List

class Solution:

	def inorder(self, n, A, res, index):
		if index >= n:
			return
		self.inorder(n, A, res, 2 * index + 1)
		res.append(A[index])
		self.inorder(n, A, res, 2 * index + 2)

	def swapReqrd(self, res, A):
		h = dict()
		for (index, val) in enumerate(res):
			h[val] = index
		count = 0
		for i in range(len(A)):
			init = res[i]
			if A[i] != res[i]:
				count += 1
				(res[i], res[h[A[i]]]) = (res[h[A[i]]], res[i])
				h[init] = h[A[i]]
				h[A[i]] = i
		return count

	def minSwaps(self, n: int, A: List[int]) -> int:
		res = []
		index = 0
		self.inorder(n, A, res, index)
		A.sort()
		return self.swapReqrd(res, A)


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		M = []

		def convert_bst_arr(A, index):
			if index >= n:
				return
			convert_bst_arr(A, 2 * index + 1)
			M.append(A[index])
			convert_bst_arr(A, 2 * index + 2)
		convert_bst_arr(A, 0)
		v = []
		for i in range(n):
			v.append([M[i], i])
		v.sort()
		swaps = 0
		i = 0
		while i < n:
			if i == v[i][1]:
				i += 1
				continue
			x = v[i][1]
			(v[i], v[x]) = (v[x], v[i])
			swaps += 1
		return swaps


from typing import List

class Solution:

	def inorder(self, a, n, index, v):
		if index >= n:
			return
		self.inorder(a, n, 2 * index + 1, v)
		v.append(a[index])
		self.inorder(a, n, 2 * index + 2, v)

	def minSwaps(self, n: int, A: List[int]) -> int:
		v = []
		self.inorder(A, n, 0, v)
		dic = {}
		vis = {}
		A.sort()
		ans = 0
		for i in range(n):
			dic[A[i]] = v[i]
			vis[A[i]] = False
		i = 0
		for i in range(n):
			cyclesize = 0
			if vis[A[i]] == False:
				j = A[i]
				while not vis[j]:
					vis[j] = True
					j = dic[j]
					cyclesize += 1
			if cyclesize > 0:
				ans += cyclesize - 1
		return ans


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		n = len(A)
		ino = []

		def solve(index):
			root = A[index]
			l = 2 * index + 1
			if l < n:
				solve(l)
			ino.append(root)
			r = 2 * index + 2
			if r < n:
				solve(r)
		solve(0)
		temp = {}
		swaps = 0
		for i in range(n):
			temp[ino[i]] = i
		temp = sorted(temp.items(), key=lambda i: i[0])
		visit = [False for _ in range(n)]
		for i in range(n):
			if visit[i] == False:
				visit[i] = True
			if temp[i][0] == ino[i]:
				continue
			else:
				index = temp[i][1]
				while visit[index] == False:
					swaps += 1
					visit[index] = True
					index = temp[index][1]
		return swaps


from typing import List

class Solution:

	def minSwaps(self, n: int, tree: List[int]) -> int:
		global l

		def minSwaps(nums):
			temp = nums.copy()
			temp.sort()
			h = {}
			for i in range(len(nums)):
				h[nums[i]] = i
			ans = 0
			init = 0
			for i in range(len(nums)):
				if temp[i] != nums[i]:
					init = nums[i]
					(nums[i], nums[h[temp[i]]]) = (nums[h[temp[i]]], nums[i])
					ans += 1
					h[init] = h[temp[i]]
					h[temp[i]] = i
			return ans

		def get_right_child(index):
			if 2 * index + 2 < n:
				return 2 * index + 2
			return -1

		def get_left_child(index):
			if 2 * index + 1 < n:
				return 2 * index + 1
			return -1

		def inorder(index):
			global l
			if index >= 0:
				inorder(get_left_child(index))
				l.append(tree[index])
				inorder(get_right_child(index))
		l = []
		inorder(0)
		ans = minSwaps(l)
		return ans


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		inorder = []
		n = len(A)

		def traversal(node):
			(left, right) = (node * 2 + 1, node * 2 + 2)
			if left < n:
				traversal(left)
			inorder.append(A[node])
			if right < n:
				traversal(right)
		traversal(0)
		inorder = [(n, i) for (i, n) in enumerate(inorder)]
		bst = sorted(inorder)
		ans = 0
		i = 0
		while i < n:
			(cur_num, cur_i) = bst[i]
			if cur_i == i:
				i += 1
				continue
			else:
				(bst[i], bst[cur_i]) = (bst[cur_i], bst[i])
				ans += 1
		return ans


from typing import List

class Entry:

	def __init__(self, val, idx):
		self.val = val
		self.idx = idx

class Solution:

	def Inorder(self, arr, node, inorder):
		if node >= len(arr):
			return
		self.Inorder(arr, 2 * node + 1, inorder)
		inorder.append(arr[node])
		self.Inorder(arr, 2 * node + 2, inorder)

	def minSwaps(self, n: int, A: List[int]) -> int:
		inorder = []
		self.Inorder(A, 0, inorder)
		arr = []
		for i in range(len(inorder)):
			val = inorder[i]
			idx = i
			temp = Entry(val, idx)
			arr.append(temp)
		arr = sorted(arr, key=lambda Entry: Entry.val)
		count = 0
		i = 0
		while i < len(arr):
			ele = arr[i]
			index = i
			while index != ele.idx:
				count += 1
				(arr[index], arr[ele.idx]) = (arr[ele.idx], arr[index])
				ele = arr[index]
			i += 1
		return count


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		ans = 0
		res = []
		temp = [0] * n
		map = {}
		self.inorder(A, n, 0, res)
		for i in range(n):
			temp[i] = res[i]
			map[res[i]] = i
		temp.sort()
		i = 0
		while i < n:
			if res[i] == temp[i]:
				i += 1
			else:
				ans += 1
				index = map.get(temp[i])
				self.swap(i, index, temp)
		return ans

	def swap(self, i, j, arr):
		(arr[i], arr[j]) = (arr[j], arr[i])

	def inorder(self, arr, n, index, res):
		if index >= n:
			return
		self.inorder(arr, n, 2 * index + 1, res)
		res.append(arr[index])
		self.inorder(arr, n, 2 * index + 2, res)


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		inorder = []
		self.find_inorder(A, inorder)
		ans = self.minimum_swaps(inorder)
		return ans

	def find_inorder(self, array, inorder, index=0):
		if index >= len(array):
			return
		self.find_inorder(array, inorder, 2 * index + 1)
		inorder.append(array[index])
		self.find_inorder(array, inorder, 2 * index + 2)

	def minimum_swaps(self, array):
		if len(array) == 0:
			return 0
		vector = []
		for i in range(len(array)):
			vector.append([array[i], i])
		vector.sort()
		i = 0
		min_swaps = 0
		while i < len(vector):
			if i != vector[i][1]:
				min_swaps += 1
				to_swap_with = vector[i][1]
				(vector[i], vector[to_swap_with]) = (vector[to_swap_with], vector[i])
			else:
				i += 1
		return min_swaps


from typing import List

class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

class Solution:

	def minSwaps(self, n: int, nums: List[int]) -> int:
		B = sorted(nums)

		def buildTree(arr, i, n):
			if i >= n:
				return None
			root = Node(arr[i])
			root.left = buildTree(arr, 2 * i + 1, n)
			root.right = buildTree(arr, 2 * i + 2, n)
			return root
		root = buildTree(nums, 0, len(nums))
		a = []

		def inorder(root):
			if root:
				inorder(root.left)
				a.append(root.data)
				inorder(root.right)
		inorder(root)

		def minSwap(nums, a):
			d = {}
			for i in range(len(nums)):
				d[nums[i]] = a[i]
			c = 0
			for i in nums:
				if i not in d:
					continue
				temp = d[i]
				temp_c = 1
				del d[i]
				while temp != i:
					temp1 = d[temp]
					del d[temp]
					temp = temp1
					temp_c += 1
				c += temp_c - 1
			return c
		return minSwap(a, B)


from typing import List

class Node:

	def __init__(self, val):
		self.data = val
		self.left = None
		self.right = None

class Solution:

	def minSwap(self, nums):
		a = nums[:]
		nums.sort()
		n = len(a)
		dic = {}
		for i in range(n):
			dic[a[i]] = i
		swap = 0
		for i in range(n):
			if nums[i] != a[i]:
				x = a[i]
				y = a[dic[nums[i]]]
				(a[dic[nums[i]]], a[i]) = (a[i], a[dic[nums[i]]])
				dic[x] = dic[nums[i]]
				dic[y] = i
				swap += 1
		return swap

	def ino(self, root, res):
		if root is None:
			return
		self.ino(root.left, res)
		res.append(root.data)
		self.ino(root.right, res)

	def minSwaps(self, n: int, A: List[int]) -> int:
		root = Node(A[0])
		q = [root]
		s = 1
		i = 1
		while s >= 0 and i < len(A):
			x = q.pop(0)
			s -= 1
			cur = A[i]
			if cur != 'N':
				x.left = Node(cur)
				q.append(x.left)
				s += 1
			i += 1
			if i >= len(A):
				break
			cur = A[i]
			if cur != 'N':
				x.right = Node(cur)
				q.append(x.right)
				s += 1
			i += 1
		res = []
		self.ino(root, res)
		return self.minSwap(res)


from typing import List

class Solution:

	def inorder(self, arr, n, index, a):
		if index >= n:
			return
		self.inorder(arr, n, 2 * index + 1, a)
		a.append(arr[index])
		self.inorder(arr, n, 2 * index + 2, a)

	def minSwap(self, arr, n):
		ans = 0
		temp = arr.copy()
		init = 0
		m = {}
		temp.sort()
		for i in range(n):
			m[arr[i]] = i
		for i in range(n):
			if temp[i] != arr[i]:
				ans += 1
				init = arr[i]
				(arr[i], arr[m[temp[i]]]) = (arr[m[temp[i]]], arr[i])
				m[init] = m[temp[i]]
				m[temp[i]] = i
		return ans

	def minSwaps(self, n: int, arr: List[int]) -> int:
		a = []
		self.inorder(arr, n, 0, a)
		return self.minSwap(a, n)


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		arr = []

		def convert(index):
			if index >= n:
				return None
			else:
				convert(2 * index + 1)
				arr.append(A[index])
				convert(2 * index + 2)

		def getMinSwaps(array):
			dp = [(array[i], i) for i in range(n)]
			dp = sorted(dp, key=lambda x: x[0])
			ans = 0
			i = 0
			while i < n:
				if dp[i][1] == i:
					i += 1
				else:
					ans += 1
					tmp = dp[i]
					dp[i] = dp[tmp[1]]
					dp[tmp[1]] = tmp
			return ans
		convert(0)
		return getMinSwaps(arr)


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		self.count = 0
		self.A = A
		self.A = self.inorder()
		self.getcount()
		return self.count

	def getcount(self):
		temparr = self.A.copy()
		h = dict()
		for i in range(len(temparr)):
			h[temparr[i]] = i
		temparr.sort()
		init = 0
		for i in range(len(temparr)):
			if temparr[i] != self.A[i]:
				self.count += 1
				init = self.A[i]
				(self.A[i], self.A[h[temparr[i]]]) = (self.A[h[temparr[i]]], self.A[i])
				h[init] = h[temparr[i]]
				h[temparr[i]] = i

	def inorder(self):
		stack = []
		curr = 0
		out = []
		while stack or curr < len(self.A):
			if curr < len(self.A):
				stack.append(curr)
				curr = 2 * curr + 1
			else:
				curr = stack.pop()
				out.append(self.A[curr])
				curr = 2 * curr + 2
		return out


from typing import List

class Solution:

	def __init__(self):
		self.r = []

	def minSwaps(self, n: int, A: List[int]) -> int:

		def f(a, index, n):
			if index >= n:
				return
			f(a, 2 * index + 1, n)
			self.r.append(a[index])
			f(a, 2 * index + 2, n)
		f(A, 0, n)
		z = sorted(self.r)
		c = 0
		for i in range(len(z) - 1):
			if z[i] != self.r[i]:
				index = -1
				c += 1
				for j in range(i + 1, len(z)):
					if self.r[j] == z[i]:
						index = j
						break
				(self.r[i], self.r[j]) = (self.r[j], self.r[i])
		return c


from typing import List
from copy import deepcopy

class Solution:

	def inorder(self, arr, v, ind):
		if ind >= len(arr):
			return
		self.inorder(arr, v, 2 * ind + 1)
		v.append(arr[ind])
		self.inorder(arr, v, 2 * ind + 2)

	def minSwap(self, nums):
		n = len(nums)
		d = {}
		for i in range(n):
			d[nums[i]] = i
		arr = deepcopy(nums)
		arr.sort()
		ans = 0
		for i in range(n):
			if arr[i] != nums[i]:
				t = d[arr[i]]
				(nums[i], nums[t]) = (nums[t], nums[i])
				d[nums[i]] = i
				d[nums[t]] = t
				ans += 1
		return ans

	def minSwaps(self, n: int, arr: List[int]) -> int:
		v = []
		self.inorder(arr, v, 0)
		return self.minSwap(v)


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		index = 0
		inordertraversal = self.convertlevortoinorder(A, index)
		swaps = self.minswapsreqtosortarray(inordertraversal)
		return swaps

	def convertlevortoinorder(self, A, index):
		inorder = []

		def levtoinconverter(A, index):
			if index >= len(A):
				return
			levtoinconverter(A, index * 2 + 1)
			inorder.append(A[index])
			levtoinconverter(A, index * 2 + 2)
		levtoinconverter(A, index)
		return inorder

	def minswapsreqtosortarray(self, nums):
		vali = []
		for i in range(len(nums)):
			vali.append([nums[i], i])
		vali.sort()
		swap = 0
		for i in range(len(nums)):
			while i != vali[i][1]:
				temp = vali[i]
				j = vali[i][1]
				vali[i] = vali[j]
				vali[j] = temp
				swap += 1
		return swap


from typing import List

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		res = []

		def inorder(index):
			if index >= n:
				return
			inorder(2 * index + 1)
			res.append(A[index])
			inorder(2 * index + 2)
		inorder(0)
		L = []
		for (i, v) in enumerate(res):
			L.append([v, i])
		L.sort()
		swaps = 0
		visited = [False] * n
		for i in range(n):
			if visited[i] or L[i][1] == i:
				continue
			cyclesize = 0
			j = i
			while not visited[j]:
				visited[j] = 1
				j = L[j][1]
				cyclesize = cyclesize + 1
			swaps = swaps + cyclesize - 1
		return swaps


from typing import List
inord = []

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		global inord
		inord = []
		self.inorder(0, A)
		arrpos = [*enumerate(inord)]
		arrpos.sort(key=lambda x: x[1])
		vis = {k: False for k in range(n)}
		ans = 0
		for i in range(n):
			if vis[i] or arrpos[i][0] == i:
				continue
			cycle_size = 0
			j = i
			while vis[j] is False:
				vis[j] = True
				cycle_size += 1
				j = arrpos[j][0]
			if cycle_size > 0:
				ans += cycle_size - 1
		return ans

	def inorder(self, root_index, arr):
		if root_index > len(arr) - 1:
			return
		self.inorder(2 * root_index + 1, arr)
		inord.append(arr[root_index])
		self.inorder(2 * root_index + 2, arr)


from typing import List
from copy import deepcopy

class Node:

	def __init__(self, val):
		self.data = val
		self.left = None
		self.right = None

class Solution:

	def minSwaps(self, n: int, A: List[int]) -> int:
		arr = []
		ino = []
		for i in range(len(A)):
			arr.append(Node(A[i]))
		for i in range(len(A) // 2):
			arr[i].left = arr[2 * i + 1]
			if 2 * i + 2 < len(A):
				arr[i].right = arr[2 * i + 2]

		def dfs(root):
			nonlocal ino
			if not root:
				return
			dfs(root.left)
			ino.append(root.data)
			dfs(root.right)
		dfs(arr[0])
		v = []
		for (ind, val) in enumerate(ino):
			v.append((val, ind))
		v.sort(key=lambda x: x[0])
		ind = 0
		cnt = 0
		while ind < n:
			if v[ind][1] == ind:
				ind += 1
				continue
			else:
				tmp = v[ind]
				tmp_ind = v[ind][1]
				v[ind] = v[v[ind][1]]
				v[tmp_ind] = tmp
				cnt += 1
		return cnt