The girl named Masha was walking in the forest and found a complete binary tree of height $n$ and a permutation $p$ of length $m=2^n$.

A complete binary tree of height $n$ is a rooted tree such that every vertex except the leaves has exactly two sons, and the length of the path from the root to any of the leaves is $n$. The picture below shows the complete binary tree for $n=2$.

A permutation is an array consisting of $n$ different integers from $1$ to $n$. For example, [$2,3,1,5,4$] is a permutation, but [$1,2,2$] is not ($2$ occurs twice), and [$1,3,4$] is also not a permutation ($n=3$, but there is $4$ in the array).

Let's enumerate $m$ leaves of this tree from left to right. The leaf with the number $i$ contains the value $p_i$ ($1 \le i \le m$).

For example, if $n = 2$, $p = [3, 1, 4, 2]$, the tree will look like this:

Masha considers a tree beautiful if the values in its leaves are ordered from left to right in increasing order.

In one operation, Masha can choose any non-leaf vertex of the tree and swap its left and right sons (along with their subtrees).

For example, if Masha applies this operation to the root of the tree discussed above, it will take the following form:

Help Masha understand if she can make a tree beautiful in a certain number of operations. If she can, then output the minimum number of operations to make the tree beautiful.


-----Input-----

The first line contains single integer $t$ ($1 \le t \le 10^4$) — number of test cases.

In each test case, the first line contains an integer $m$ ($1 \le m \le 262144$), which is a power of two  — the size of the permutation $p$.

The second line contains $m$ integers: $p_1, p_2, \dots, p_m$ ($1 \le p_i \le m$) — the permutation $p$.

It is guaranteed that the sum of $m$ over all test cases does not exceed $3 \cdot 10^5$.


-----Output-----

For each test case in a separate line, print the minimum possible number of operations for which Masha will be able to make the tree beautiful or -1, if this is not possible.


-----Examples-----

Input
4
8
6 5 7 8 4 3 1 2
4
3 1 4 2
1
1
8
7 8 4 3 1 2 6 5
Output
4
-1
0
-1


-----Note-----

Consider the first test.

In the first test case, you can act like this (the vertex to which the operation is applied at the current step is highlighted in purple):

It can be shown that it is impossible to make a tree beautiful in fewer operations.

In the second test case, it can be shown that it is impossible to make a tree beautiful.

In the third test case, the tree is already beautiful.

Difficulty: EASY
Tags: Graph algorithms

Graph traversal

Sorting

Tree algorithms

Divide and conquer
Skill types: Sorting

Starter code:

Solutions:
def beat(arr):
	n_swap = 0
	mult = 2
	while mult <= len(arr):
		for i in range(0, len(arr), mult):
			if abs(arr[i] - arr[i + mult // 2]) < mult:
				if arr[i] > arr[i + mult // 2]:
					n_swap += 1
			else:
				return -1
		mult = mult * 2
	return n_swap
k = int(input())
for i in range(k):
	n = int(input())
	arr = [int(j) for j in input().split()]
	print(beat(arr))


import collections
import heapq
import sys
import math
import itertools
import bisect
from io import BytesIO, IOBase
import os

def values():
	return list(map(int, sys.stdin.readline().split()))

def inlsts():
	return [int(i) for i in sys.stdin.readline().split()]

def inp():
	return int(sys.stdin.readline())

def instr():
	return sys.stdin.readline().strip()

def words():
	return [i for i in sys.stdin.readline().strip().split()]

def chars():
	return [i for i in sys.stdin.readline().strip()]

def solve():
	n = inp()
	l = values()
	x = 1
	ans = 0
	while x < n:
		for i in range(0, n, 2 * x):
			if abs(l[i] - l[i + x]) != x:
				ans = -1
				break
			if l[i] > l[i + x]:
				(l[i], l[x + i]) = (l[x + i], l[i])
				ans += 1
		x *= 2
		if ans == -1:
			break
	print(ans)
for i in range(inp()):
	solve()


x = int(input())

def do(n, lis):
	res = 0
	for p in range(len(bin(n)) - 3):
		k = 2 ** p
		for q in range(0, n - 1, k * 2):
			if lis[q] - lis[q + k] == k:
				lis[q] -= k
				res += 1
			elif lis[q + k] - lis[q] != k:
				return -1
	return res
for _ in range(x):
	a = int(input())
	b = list(map(int, input().split()))
	print(do(a, b))


from math import inf
import sys

def main():
	input = sys.stdin.readline
	t = int(input())
	for _ in range(t):
		n = int(input())
		(*leafs,) = map(int, input().split())
		auxLeafs = []
		ans = 0
		multi = 1
		while len(leafs) > 1 and ans != -1:
			for i in range(1, len(leafs), 2):
				if leafs[i - 1] > leafs[i]:
					ans += 1
					(leafs[i], leafs[i - 1]) = (leafs[i - 1], leafs[i])
				if leafs[i] - leafs[i - 1] > multi:
					ans = -1
					leafs = []
					break
				auxLeafs.append(leafs[i - 1])
			leafs = auxLeafs.copy()
			auxLeafs = []
			multi = multi * 2
		print(ans)
main()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	hop = 2
	while hop <= n:
		for i in range(0, n, hop):
			v = arr[i] - arr[i + hop // 2]
			if abs(v) >= hop:
				ans = -1
				break
			elif v > 0:
				ans += 1
		hop *= 2
		if ans == -1:
			break
	print(ans)


def dfs(ls, l, r):
	if l + 1 == r:
		if ls[l] < ls[r]:
			return (0, ls[l], ls[r])
		else:
			return (1, ls[r], ls[l])
	mid = (l + r) // 2
	(ans1, lo1, hi1) = dfs(ls, l, mid)
	(ans2, lo2, hi2) = dfs(ls, mid + 1, r)
	if ans1 == -1 or ans2 == -1:
		return (-1, -1, -1)
	if hi1 < hi2:
		if hi1 + 1 == lo2:
			return (ans1 + ans2, lo1, hi2)
		return (-1, -1, -1)
	else:
		if hi2 + 1 == lo1:
			return (1 + ans1 + ans2, lo2, hi1)
		return (-1, -1, -1)

def foo(n, ls):
	if n == 1:
		return 0
	(ans, lo, hi) = dfs(ls, 0, n - 1)
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	ls = [int(i) for i in input().split()]
	print(foo(n, ls))


def solve():
	n = int(input())
	lis = list(map(int, input().split()))
	step = 1
	ans = int()
	while step < n:
		for i in range(0, n, 2 * step):
			if lis[i] > lis[i + step]:
				(lis[i:i + step], lis[i + step:i + step * 2]) = (lis[i + step:i + step * 2], lis[i:i + step])
				ans += 1
		step *= 2
	print(ans if lis == list(range(1, n + 1)) else -1)
for _ in range(int(input())):
	solve()


from audioop import mul
import sys

def beat(arr):
	n_swap = 0
	mult = 2
	while mult <= len(arr):
		for i in range(0, len(arr), mult):
			if abs(arr[i] - arr[i + mult // 2]) < mult:
				if arr[i] > arr[i + mult // 2]:
					arr[i] = arr[i + mult // 2]
					n_swap += 1
			else:
				return -1
		mult = mult * 2
	return n_swap
k = int(input())
for i in range(k):
	n = int(input())
	arr = [int(j) for j in input().split()]
	print(beat(arr))


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	s = 1
	ans = int()
	while s < n:
		for i in range(0, n, 2 * s):
			if a[i] > a[i + s]:
				(a[i:i + s], a[i + s:i + s * 2]) = (a[i + s:i + s * 2], a[i:i + s])
				ans += 1
		s *= 2
	print(ans if a == list(range(1, n + 1)) else -1)
for _ in range(int(input())):
	solve()


from heapq import heappush, heappop, heapify
from collections import Counter

def getIntegerInputs():
	return map(int, input().split())

def getListInput():
	return list(map(int, input().split()))

def inbound(r, c, n, m):
	return 0 <= r < n and 0 <= c < m

def solve():
	for _ in range(int(input())):
		n = int(input())
		arr = getListInput()
		(x, ans) = (1, 0)
		while x < n:
			for i in range(0, n, 2 * x):
				if abs(arr[i] - arr[i + x]) != x:
					ans = -1
					break
				if arr[i] > arr[i + x]:
					(arr[i], arr[x + i]) = (arr[x + i], arr[i])
					ans += 1
			x *= 2
			if ans == -1:
				break
		print(ans)
solve()


import sys
input = sys.stdin.readline
import math
from collections import defaultdict

def print_str_line(str):
	sys.stdout.write(str + '\n')

def print_number(number):
	print_str_line(f'{number}')

def read_list_of_integers():
	return [int(num) for num in input()[:-1].split(' ')]

def is_permutation_beautifiable(permutation):
	i = 2
	while i < len(permutation):
		for j in range(0, len(permutation), i):
			first_num = permutation[j]
			second_num = permutation[j + i // 2]
			if abs(first_num - second_num) >= i:
				return False
		i *= 2
	return True

def solve(permutation):
	if not is_permutation_beautifiable(permutation):
		return -1
	i = 2
	ans = 0
	while i <= len(permutation):
		for j in range(0, len(permutation), i):
			first_num = permutation[j]
			second_num = permutation[j + i // 2]
			if first_num > second_num:
				ans += 1
		i *= 2
	return ans

def main():
	numer_of_test_cases = int(input()[:-1])
	for i in range(numer_of_test_cases):
		permutation_size = int(input()[:-1])
		permutation = read_list_of_integers()
		_ans = solve(permutation)
		print_number(_ans)
main()


def beautifullization(p):
	n = 0
	newP = []
	if len(p) == 1:
		return 0
	for i in range(len(p) // 2):
		(n1, n2) = (p[2 * i], p[2 * i + 1])
		if abs(n1 - n2) != 1:
			return -1
		elif n1 > n2:
			n += 1
			newP.append(n1 // 2)
		else:
			newP.append(n2 // 2)
	deeperN = beautifullization(newP)
	if deeperN == -1:
		return -1
	else:
		return n + deeperN
for _ in range(int(input())):
	m = int(input())
	p = list(map(int, input().split()))
	n = beautifullization(p)
	print(n)


def go(a, n):
	ans = 0
	if n == 1:
		return 0
	x = 1
	while len(a) != 1:
		new_a = []
		for i in range(0, len(a), 2):
			if abs(a[i] - a[i + 1]) != x:
				return -1
			if a[i] < a[i + 1]:
				new_a.append(a[i])
			else:
				ans += 1
				new_a.append(a[i + 1])
		x = x * 2
		a = new_a
	return ans
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(go(a, n))


def solve(a):
	n = len(a)
	if n == 1:
		return 0
	cnt = 0
	arr = []
	for i in range(0, n, 2):
		if abs(a[i] - a[i + 1]) == 1:
			if a[i] > a[i + 1]:
				cnt += 1
				(a[i + 1], a[i]) = (a[i], a[i + 1])
			arr.append(a[i + 1] / 2)
		else:
			return float('inf')
	return cnt + solve(arr)
for test in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	res = solve(a)
	if res == float('inf'):
		res = -1
	print(res)


def S(a, m):
	j = 1
	b = list(range(1, m + 1))
	count = 0
	while j < m:
		j = j * 2
		for i in range(0, m, j):
			x = i + j
			(k, l) = (i, i + j // 2)
			if a[k] > a[l]:
				count += 1
				(a[k:l], a[l:i + j]) = (a[l:i + j], a[k:l])
	if a != b:
		return -1
	return count
for i in range(int(input())):
	m = int(input())
	a = list(map(int, input().split()))
	print(S(a, m))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = 1
	ans = 0
	chk = 0
	while x < n:
		for i in range(0, n, 2 * x):
			if abs(a[i] - a[i + x]) == x:
				if a[i] > a[i + x]:
					t = a[i]
					a[i] = a[i + x]
					a[i + x] = t
					ans += 1
			else:
				chk = 1
				print(-1)
				break
		if chk:
			break
		x = x * 2
	else:
		print(ans)


def ss(a, n):
	j = 1
	b = list(range(1, n + 1))
	count = 0
	while j < n:
		j = j * 2
		for i in range(0, n, j):
			x = i + j
			(k, l) = (i, i + j // 2)
			if a[k] > a[l]:
				count += 1
				(a[k:l], a[l:i + j]) = (a[l:i + j], a[k:l])
	if a != b:
		return -1
	return count
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(ss(a, n))


def solve():
	n = int(input())
	ls = list(map(int, input().split()))
	for i in range(n):
		ls[i] = ls[i] - 1
	f = 1
	ans = 0
	while len(ls) > 1:
		nt = []
		for i in range(0, len(ls), 2):
			if abs(ls[i + 1] - ls[i]) > 1:
				f = 0
				break
			if ls[i + 1] < ls[i]:
				ans += 1
			nt.append(ls[i] // 2)
		ls = nt
		if not f:
			break
	if f:
		print(ans)
	else:
		print(-1)
for i in range(int(input())):
	solve()


def ans(a, cnt):
	if len(a) == 1:
		return cnt
	b = []
	for i in range(0, len(a), 2):
		if a[i + 1] < a[i]:
			c = a[i + 1]
			a[i + 1] = a[i]
			a[i] = c
			cnt += 1
		if a[i + 1] - a[i] == 1:
			b.append(a[i + 1] // 2)
		else:
			return -1
	return ans(b, cnt)
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(ans(a, 0))


def solve(n, arr):
	if n == 1:
		return 0
	lt = []
	cnt = 0
	for i in range(n // 2):
		if arr[2 * i] & 1 == 0:
			if arr[2 * i + 1] != arr[2 * i] - 1:
				return -1
			else:
				cnt += 1
				lt.append(arr[2 * i] // 2)
		if arr[2 * i] & 1 == 1:
			if arr[2 * i + 1] != arr[2 * i] + 1:
				return -1
			else:
				lt.append(arr[2 * i + 1] // 2)
	ans = solve(n // 2, lt)
	if ans == -1:
		return -1
	return cnt + ans

def main():
	n = int(input())
	txt = input()
	lt = list(map(int, txt.split(' ')))
	print(solve(n, lt))
t = int(input())
for test in range(t):
	main()


for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	(l, swaps) = (1, 0)
	while l < n:
		for i in range(0, n, 2 * l):
			if L[i] > L[i + l]:
				(L[i:i + l], L[i + l:i + 2 * l]) = (L[i + l:i + 2 * l], L[i:i + l])
				swaps += 1
		l <<= 1
	print(swaps if L == sorted(L) else -1)


for _ in range(int(input())):
	n = int(input())
	p = [*map(int, input().split())]
	(j, ans, f) = (1, 0, 0)
	while j < n:
		for i in range(0, n, j * 2):
			if abs(p[i] - p[i + j]) != j:
				f = 1
			if p[i] > p[i + j]:
				(p[i], p[i + j], ans) = (p[i + j], p[i], ans + 1)
		j <<= 1
	print([ans, -1][f])


for i in range(int(input())):
	m = int(input())
	arr = list(map(int, input().split()))
	if m == 1:
		print(0)
	else:
		ws = 1
		ans = 0
		flag = True
		while ws < m:
			for i in range(0, m, ws * 2):
				if abs(arr[i] - arr[i + ws]) != ws:
					flag = False
				if arr[i] > arr[i + ws]:
					(arr[i], arr[i + ws]) = (arr[i + ws], arr[i])
					ans += 1
			ws <<= 1
		if flag == False:
			print(-1)
		else:
			print(ans)


t = int(input())
m = 1000000000.0 + 7

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	diff = 1
	ans = 0
	while True:
		lst = []
		for i in range(1, len(arr), 2):
			if abs(arr[i] - arr[i - 1]) != diff:
				print(-1)
				return
			if arr[i] < arr[i - 1]:
				ans = ans + 1
			lst.append(min(arr[i], arr[i - 1]))
		arr = lst
		diff = diff << 1
		if len(lst) == 0:
			print(ans)
			return
for _ in range(t):
	solve()


from sys import stdin
input = lambda : stdin.readline()
for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	(l, swaps) = (1, 0)
	while l < n:
		for i in range(0, n, 2 * l):
			if L[i] > L[i + l]:
				(L[i:i + l], L[i + l:i + 2 * l]) = (L[i + l:i + 2 * l], L[i:i + l])
				swaps += 1
		l <<= 1
	print(swaps if L == sorted(L) else -1)


import math
t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	if n == 1:
		if s[0] == 1:
			print(0)
		else:
			print(-1)
	else:
		tmp = []
		ans = 0
		diff = 1
		cnt = 1
		while len(s) != 1:
			flag = 0
			for i in range(0, len(s) - 1, 2):
				if abs(s[i] - s[i + 1]) != diff:
					flag = 1
					break
				if s[i] > s[i + 1]:
					tmp.append(s[i + 1])
					ans += 1
				else:
					tmp.append(s[i])
			if flag:
				break
			s = tmp
			tmp = []
			diff = math.pow(2, cnt)
			cnt += 1
		if flag:
			print(-1)
		else:
			print(ans)


def find_swaps(units):
	if len(units) == 1:
		return 0
	new_units = []
	count = 0
	for i in range(len(units)):
		if i % 2 == 0:
			(min1, max1) = units[i]
			(min2, max2) = units[i + 1]
			if max1 < min2:
				new_units.append((min1, max2))
			elif max2 < min1:
				count += 1
				new_units.append((min2, max1))
			else:
				return -1
	v = find_swaps(new_units.copy())
	if v == -1:
		return -1
	return v + count
t = int(input())
for _ in range(t):
	m = int(input())
	perms = list(map(int, input().split()))
	units = [(k, k) for k in perms]
	print(find_swaps(units))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = [a[i] - 1 for i in range(n)]
	ans1 = 0
	flag = True
	while len(a) > 1:
		ans = []
		for i in range(0, len(a), 2):
			if abs(a[i + 1] - a[i]) > 1:
				flag = False
				break
			if a[i + 1] < a[i]:
				ans1 += 1
			ans.append(a[i] // 2)
		a = ans
		if not flag:
			break
	if flag:
		print(ans1)
	else:
		print(-1)


import sys, random
input = lambda : sys.stdin.readline().rstrip()
for _ in range(int(input())):
	a = int(input())
	p = list(map(int, input().split()))
	if a == 1:
		print(0)
		continue
	flg = 1
	ans = 0
	for i in range(a.bit_length() - 1):
		k = 2 ** i
		for j in range(0, a, k * 2):
			if p[j] > p[j + k]:
				(p[j], p[j + k]) = (p[j + k], p[j])
				ans += 1
			if abs(p[j] - p[j + k]) != k:
				flg = 0
	print(ans if flg else -1)


def solve(xs):
	out = 0
	while len(xs) != 1:
		tmp = [0] * (len(xs) >> 1)
		for i in range(len(tmp)):
			left = (xs[i << 1] + 1) // 2
			right = (xs[(i << 1) + 1] + 1) // 2
			if left != right:
				print(-1)
				return
			if xs[i << 1] > xs[(i << 1) + 1]:
				out += 1
			tmp[i] = left
		xs = tmp
	print(out)
for _ in range(int(input())):
	input()
	xs = list(map(int, input().split()))
	solve(xs)


from math import log2

def ii() -> list:
	return list(map(int, input().split()))
t = int(input())
for _ in range(t):
	n = int(input())
	tree = ii()
	res = 0
	for parent_i in range(int(log2(n))):
		step = 2 ** (parent_i + 1)
		low = tree[::step]
		high = tree[step - 1::step]
		for i in range(n // step):
			if low[i] > high[i]:
				res += 1
				ff = step * i
				fs = step * i + step - step // 2
				sf = step * (i + 1) - step // 2
				ss = step * (i + 1)
				(tree[ff:fs], tree[sf:ss]) = (tree[sf:ss], tree[ff:fs])
	print(res if sorted(tree) == tree else -1)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(x, ans) = (1, 0)
	while x < n:
		for i in range(0, n, 2 * x):
			if abs(arr[i] - arr[i + x]) != x:
				ans = -1
				break
			if arr[i] > arr[i + x]:
				(arr[i], arr[i + x]) = (arr[i + x], arr[i])
				ans += 1
		x *= 2
		if ans == -1:
			break
	print(ans)


for t in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	state = 1
	k = 0
	for i in range(0, n - 1, 2):
		if p[i] > p[i + 1]:
			k += 1
			(p[i], p[i + 1]) = (p[i + 1], p[i])
		if p[i + 1] - p[i] > 1:
			state = 0
	kol = 2
	while kol < n:
		for i in range(0, n, kol * 2):
			if p[i] > p[kol + i]:
				(p[i:kol + i], p[kol + i:kol + i + kol]) = (p[kol + i:kol + i + kol], p[i:kol + i])
				k += 1
			if p[kol + i] - p[i] > kol:
				state = 0
		kol *= 2
	print([-1, k][state])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	nn = n
	z = a[0:]
	x = []
	c = 1
	e = 0
	r = 0
	while nn > 1:
		i = 0
		while i < nn:
			if z[i] > z[i + 1]:
				if z[i] - z[i + 1] != c:
					e = 1
					break
				else:
					r += 1
					x.append(z[i])
			elif z[i + 1] - z[i] != c:
				e = 1
				break
			else:
				x.append(z[i + 1])
			i += 2
		if e == 1:
			break
		else:
			z = x[0:]
			x = []
			nn = len(z)
			c *= 2
	if e == 1:
		print(-1)
	else:
		print(r)


def N():
	return int(input())

def A():
	return [int(x) for x in input().split()]

def S():
	return input()
for _ in range(N()):
	n = N()
	if 'er9fj48gh48gh4' == 14194665565:
		print('Tanmay')
	a = A()
	d = 1
	c = 0
	cc = 1
	f = True
	for i in range(int(n ** 0.5) + 1):
		aa = []
		for i in range(0, len(a), 2):
			if len(a) == 1:
				break
			if abs(a[i] - a[i + 1]) != d:
				f = False
				break
			if a[i] > a[i + 1]:
				aa.append(a[i + 1])
				c += 1
				continue
			else:
				aa.append(a[i])
		if not f:
			break
		d *= 2
		a = aa.copy()
	if f:
		print(c)
		continue
	print(-1)


from math import log2
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	steps = 0
	t = 1
	if n == 1:
		print(0)
		continue
	for i in range(0, n, 2):
		if a[i + 1] < a[i]:
			(a[i], a[i + 1]) = (a[i + 1], a[i])
			steps += 1
	par = True
	for x in range(int(log2(n)) - 1):
		flag = True
		t *= 2
		for i in range(0, n, t * 2):
			l = a[i:i + t]
			r = a[i + t:i + 2 * t]
			if l[0] > r[0]:
				(a[i:i + t], a[i + t:i + 2 * t]) = (r, l)
				(l, r) = (r, l)
				steps += 1
			if l[0] < r[0] < l[-1]:
				flag = False
				break
		if flag == False:
			par = False
			break
	if par == False:
		print(-1)
	else:
		print(steps)


def is_valid(left, right):
	return left // 2 == right // 2

def need_swap(left, right):
	return left > right

def swap_layer(layer):
	swaps = 0
	parent_layer = []
	for i in range(0, len(layer), 2):
		(left, right) = (layer[i], layer[i + 1])
		if not is_valid(left, right):
			return (-1, [])
		if need_swap(left, right):
			swaps += 1
		parent_layer.append(left // 2)
	return (swaps, parent_layer)

def solve(layer):
	if len(layer) == 1:
		return 0
	swaps = 0
	while len(layer) > 1:
		(count, layer) = swap_layer(layer)
		if count == -1:
			return -1
		swaps += count
	return swaps
for _ in range(int(input())):
	input()
	tree = list(map(int, input().split()))
	tree = [t - 1 for t in tree]
	print(solve(tree))


def f(arr, l, r):
	if r - l == 1:
		if arr[l] > arr[r]:
			(arr[l], arr[r]) = (arr[r], arr[l])
			return 1
		return 0
	mid = (r + l) // 2
	a = f(arr, l, mid)
	b = f(arr, mid + 1, r)
	if a == -1 or b == -1 or arr[mid] - arr[l] != mid - l or (arr[r] - arr[mid + 1] != mid - l):
		return -1
	result = a + b
	if arr[l] > arr[mid + 1]:
		(arr[l:mid + 1], arr[mid + 1:r + 1]) = (arr[mid + 1:r + 1], arr[l:mid + 1])
		return result + 1
	return result
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		print(f(arr, 0, n - 1))


from sys import stdin
for _ in range(int(stdin.readline())):
	m = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	ln = 1
	moves = 0
	while ln < m:
		for i in range(0, m, ln * 2):
			if a[i + ln - 1] > a[i + ln]:
				if a[i] > a[i + ln * 2 - 1]:
					(a[i:i + ln], a[i + ln:i + ln * 2]) = (a[i + ln:i + ln * 2], a[i:i + ln])
					moves += 1
				else:
					print(-1)
					break
		else:
			ln *= 2
			continue
		break
	else:
		print(moves)


def check_sorted(L):
	for i in range(len(L) - 1):
		if L[i] > L[i + 1]:
			return False
	return True
for _ in range(int(input())):
	n = int(input())
	L = list(map(int, input().split()))
	(l, swaps) = (1, 0)
	while l < n:
		for i in range(0, n, 2 * l):
			if L[i] > L[i + l]:
				(L[i:i + l], L[i + l:i + 2 * l]) = (L[i + l:i + 2 * l], L[i:i + l])
				swaps += 1
		l <<= 1
	print(swaps if check_sorted(L) else -1)


l = []
for _ in range(int(input())):
	m = int(input())
	p = [int(j) for j in input().split()]
	p2 = []
	s = 0
	step = 1
	while len(p) > 1 and s >= 0:
		for j in range(0, len(p) - 1, 2):
			if abs(p[j] - p[j + 1]) != step:
				s = -1
				break
			if p[j] < p[j + 1]:
				p2.append(p[j])
			else:
				s += 1
				p2.append(p[j + 1])
		p = p2.copy()
		p2 = []
		step *= 2
	l.append(s)
for i in l:
	print(i)


from math import log
for pratyush in range(int(input())):
	n = int(input())
	m = int(log(n) / log(2))
	a = list(map(int, input().split()))
	b = sorted(a)
	if a == b:
		print(0)
		continue
	ans = 0
	for x in range(1, m + 1):
		p = 2 ** x
		q = 2 ** (x - 1)
		for y in range(0, n, p):
			if a[y] > a[y + q]:
				(a[y:y + q], a[y + q:y + p]) = (a[y + q:y + p], a[y:y + q])
				ans += 1
	if a != b:
		print(-1)
		continue
	print(ans)


for _ in range(int(input())):
	m = int(input())
	a = list(map(int, input().split()))
	ln = 1
	moves = 0
	while ln < m:
		for i in range(0, m, ln * 2):
			if a[i + ln - 1] > a[i + ln]:
				if a[i] > a[i + ln * 2 - 1]:
					(a[i:i + ln], a[i + ln:i + ln * 2]) = (a[i + ln:i + ln * 2], a[i:i + ln])
					moves += 1
				else:
					print(-1)
					break
		else:
			ln *= 2
			continue
		break
	else:
		print(moves)


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(i) for i in input().split(' ')]
	flag = False
	steps = 0
	while n > 1:
		newArr = [-1 for i in range(n // 2)]
		for i in range(n // 2):
			if arr[2 * i] == arr[2 * i + 1] - 1:
				newArr[i] = arr[2 * i + 1] // 2
			elif arr[2 * i] == arr[2 * i + 1] + 1:
				steps += 1
				newArr[i] = arr[2 * i] // 2
			else:
				flag = True
				break
		arr = newArr
		n = n // 2
	if flag == True:
		print(-1)
	else:
		print(steps)


import sys
sys.setrecursionlimit(10 ** 7)
t = int(input())
for _ in range(t):
	m = int(input())
	P = list(map(int, input().split()))

	def dp(i, j):
		if i == j:
			return (0, P[i], P[i])
		mid = (i + j + 1) // 2
		l = dp(i, mid - 1)
		r = dp(mid, j)
		if l[2] < r[1]:
			return (l[0] + r[0], l[1], r[2])
		elif l[1] > r[2]:
			return (l[0] + r[0] + 1, r[1], l[2])
		return (float('inf'), float('inf'), -float('inf'))
	res = dp(0, m - 1)
	if res[0] == float('inf'):
		print(-1)
	else:
		print(res[0])


def switch(a, i):
	t1 = a[:i]
	t2 = a[i:]
	t = t2 + t1
	return t
test = int(input())
while test > 0:
	n = int(input())
	a = [int(x) for x in input().split()]
	i = 1
	count = 0
	while i <= n // 2:
		for j in range(0, n, 2 * i):
			k = j + 2 * i - 1
			if a[j] > a[k]:
				t = switch(a[j:k + 1], i)
				count += 1
				a[j:k + 1] = t
		i *= 2
	b = [x for x in range(1, n + 1)]
	if a == b:
		print(count)
	else:
		print('-1')
	test -= 1


import sys
input = sys.stdin.readline
for i in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	p = 1
	ans = 0
	while p < n:
		for i in range(0, n - p * 2 + 1, p * 2):
			if a[i + p - 1] > a[i + p]:
				(a[i:i + p], a[i + p:i + p + p]) = (a[i + p:i + p + p], a[i:i + p])
				ans += 1
		p *= 2
	if a == list(range(1, n + 1)):
		print(ans)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) - 1 for i in input().split()]
	s = 0
	imp = False
	while len(a) > 1:
		b = []
		for i in range(0, len(a) - 1, 2):
			if abs(a[i] - a[i + 1]) != 1:
				imp = True
				break
			if a[i] > a[i + 1]:
				s += 1
			b.append(min(a[i], a[i + 1]) // 2)
		if imp:
			print(-1)
			break
		a = b
	else:
		print(s)


import sys
readline = sys.stdin.readline
T = int(readline())
for _ in range(T):
	N = int(readline())
	P = list(map(int, readline().split()))
	tmp = []
	flag = True
	ans = 0
	if len(P) == 1:
		print(0)
		continue
	for i in range(0, N, 2):
		(a, b) = P[i:i + 2]
		if a > b:
			(a, b) = (b, a)
			ans += 1
		tmp.append([a, b])
	while len(tmp) > 1:
		n = len(tmp)
		nxt = []
		for i in range(0, n, 2):
			(a, b) = tmp[i:i + 2]
			if a > b:
				ans += 1
				(a, b) = (b, a)
			if a[1] + 1 == b[0]:
				nxt.append([a[0], b[1]])
			else:
				flag = False
		if flag:
			tmp = nxt
		else:
			break
	if flag:
		print(ans)
	else:
		print(-1)


t = int(input())
for i in range(t):
	m = int(input())
	a = list(map(int, input().split(' ')))

	def swap(i, j):
		x = a[i:i + j]
		a[i:i + j] = a[i + j:i + 2 * j]
		a[i + j:i + 2 * j] = x
	q = 2
	cnt = 0
	while q <= m:
		for i in range(0, m, q):
			if a[i] > a[i + q // 2]:
				cnt += 1
				swap(i, q // 2)
		q *= 2
	f = 0
	for i in range(1, m):
		if a[i] == a[i - 1] + 1:
			continue
		else:
			f = 1
			print(-1)
			break
	if f == 0:
		print(cnt)


t = int(input())

def sort(arr, i, j):
	if i + 1 >= j:
		ctr = 0
		if arr[i] > arr[j]:
			ctr = 1
		valid = True
		if abs(arr[i] - arr[j]) > 1:
			valid = False
		return (min(arr[i], arr[j]), max(arr[i], arr[j]), ctr, valid)
	mid = (i + j) // 2
	ctr = 0
	(lmin, lmax, x, lvalid) = sort(arr, i, mid)
	(rmin, rmax, y, rvalid) = sort(arr, mid + 1, j)
	cmin = min(lmin, rmin)
	cmax = max(lmax, rmax)
	valid = lvalid and rvalid
	if cmax - cmin != j - i:
		valid = False
	if lmin > rmin:
		ctr += 1
	return (cmin, cmax, x + y + ctr, valid)
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	(amin, amax, res, valid) = sort(arr, 0, n - 1)
	if not valid:
		print(-1)
	else:
		print(res)


def isBeautiful(a, l, r):
	if r - l == 1:
		return (0, a[l], a[l])
	mid = (l + r) // 2
	(ll, ls, lb) = isBeautiful(a, l, mid)
	(rr, rs, rb) = isBeautiful(a, mid, r)
	(ss, bb) = (min(ls, rs), max(lb, rb))
	if ll == -1 or rr == -1:
		return (-1, ss, bb)
	if lb < rs:
		return (ll + rr, ss, bb)
	if ls > rb:
		return (ll + rr + 1, ss, bb)
	return (-1, ss, bb)
t = int(input())
for _ in range(t):
	m = int(input())
	p = list(map(int, input().split()))
	(ans, sm, bi) = isBeautiful(p, 0, m)
	print(ans)


for t in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	k = 0
	for i in range(0, n - 1, 2):
		if p[i] > p[i + 1]:
			k += 1
			(p[i], p[i + 1]) = (p[i + 1], p[i])
		if p[i + 1] - p[i] > 1:
			print(-1)
			break
	else:
		kol = 2
		while kol < n:
			for i in range(0, n - kol, kol * 2):
				if p[i] > p[kol + i] or p[i + 1] > p[kol + 1 + i]:
					(p[i:kol + i], p[kol + i:kol + i + kol]) = (p[kol + i:kol + i + kol], p[i:kol + i])
					k += 1
				if p[kol + i] - p[i] > kol or p[kol + 1 + i] - p[i + 1] > kol:
					print(-1)
					break
			else:
				kol *= 2
				continue
			break
		else:
			print(k)


def mergeSort(arr, curr):
	if len(arr) > 1:
		mid = len(arr) // 2
		L = arr[:mid]
		R = arr[mid:]
		mergeSort(L, curr)
		mergeSort(R, curr)
		i = j = k = 0
		if L < R:
			arr[:mid] = L
			arr[mid:] = R
		else:
			counts[curr] += 1
			arr[:mid] = R
			arr[mid:] = L

def printList(arr):
	for i in range(len(arr)):
		print(arr[i], end=' ')
	print()

def next_power_of_2(x):
	return 1 if x == 0 else 2 ** (x - 1).bit_length()
t = int(input())
counts = [0 for i in range(t)]
for i in range(t):
	n = int(input())
	arr = list(map(int, input().rstrip().split()))
	nearest = next_power_of_2(n)
	for j in range(n, nearest):
		arr.append(0)
	mergeSort(arr, i)
	if all((arr[i] <= arr[i + 1] for i in range(len(arr) - 1))):
		pass
	else:
		counts[i] = -1
for i in counts:
	print(i)


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(a, l, r):
	if l == r:
		return 0
	m = (l + r) // 2
	left = solve(a, l, m)
	right = solve(a, m + 1, r)
	if left == -1 or right == -1:
		return -1
	res = left + right
	if a[r] < a[l]:
		(a[l:m + 1], a[m + 1:r + 1]) = (a[m + 1:r + 1], a[l:m + 1])
		res += 1
	elif a[m] > a[m + 1]:
		return -1
	return res
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(solve(a, 0, n - 1))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	b = 1
	ok = True
	while len(a) > 1:
		tmp = []
		for i in range(0, len(a), 2):
			if abs(a[i] - a[i + 1]) != b:
				ok = False
			if a[i] > a[i + 1]:
				ans += 1
			tmp.append(max(a[i], a[i + 1]))
		b *= 2
		a = tmp.copy()
	print(ans if ok else -1)


import math

def cu(Se, h, num, ans):
	for g in range(0, num, 2):
		if Se[g] - Se[g + 1] == 4 ** (h - 1):
			ans += 1
		elif abs(Se[g] - Se[g + 1]) != 4 ** (h - 1):
			ans = -1
			return ans
	t = int(num / 2)
	S = [None for m in range(t)]
	for g1 in range(t):
		S[g1] = Se[2 * g1 + 1] + Se[2 * g1]
	Se[:] = S[:]
	return ans
n = int(input())
for i in range(n):
	ans = 0
	num = int(input())
	h = int(math.log2(num))
	x = input()
	Se = [int(n1) for n1 in x.split()]
	for g in range(1, h + 1):
		ans = cu(Se, g, num, ans)
		num = int(num / 2)
		if ans == -1:
			break
	print(ans)


ans = 0

def recur(arr):
	global ans
	if len(arr) == 2:
		if arr[1] >= arr[0]:
			return arr
		else:
			ans += 1
			(arr[1], arr[0]) = (arr[0], arr[1])
			return arr
	n = len(arr)
	mid = n // 2
	if sum(arr[:mid]) > sum(arr[mid:]):
		ans += 1
		a = recur(arr[mid:])
		b = recur(arr[:mid])
		return a + b
	else:
		a = recur(arr[:mid])
		b = recur(arr[mid:])
		return a + b

def check(arr) -> bool:
	for i in range(0, len(arr), 2):
		if abs(arr[i] - arr[i + 1]) != 1:
			return False
	return True

def sorted(arr):
	for i in range(1, len(arr)):
		if arr[i] < arr[i - 1]:
			return False
	return True

def solve():
	global ans
	ans = 0
	n = int(input())
	arr = list(map(int, input().split(' ')))
	if n == 1:
		return 0
	if check == False:
		return -1
	if sorted(recur(arr)):
		return ans
	return -1
test = int(input())
for _ in range(test):
	ans = solve()
	print(ans)


import sys
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))

	def solve(arr, n1):
		if len(arr) == 1:
			return 0
		t = []
		c = 0
		for i in range(0, n1, 2):
			if min(arr[i], arr[i + 1]) + 1 != max(arr[i], arr[i + 1]):
				return float('inf')
			if arr[i] > arr[i + 1]:
				c += 1
			t.append(max(arr[i], arr[i + 1]) // 2)
		return c + solve(t, n1 // 2)
	t1 = solve(l, n)
	if t1 == float('inf'):
		print(-1)
	else:
		print(t1)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(0)
		return
	b = [(a[i], i + 1) for i in range(n)]
	b = sorted(b)
	ans = 0
	step = 2
	ds = [1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143]
	iss = 0
	while step < n:
		for i in range(0, n, step):
			if abs(b[i][1] - b[i + step // 2][1]) > ds[iss]:
				print(-1)
				return
			if b[i][1] > b[i + step // 2][1]:
				ans += 1
		step *= 2
		iss += 1
	if b[0][1] > n // 2:
		ans += 1
	print(ans)
for T in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	res = 0
	curr = 0
	solved = False
	while 1 << curr < n:
		if n == 1:
			if l[0] != 1:
				solved = True
				print(-1)
			break
		addon = 1 << curr
		for i in range(0, n, addon << 1):
			high = max(l[i], l[i + addon])
			low = min(l[i], l[i + addon])
			if high - low != addon:
				solved = True
				print(-1)
				break
			if l[i] != low:
				res += 1
				l[i] = low
		if solved:
			break
		curr += 1
	if not solved:
		print(res)


global counter

def flip(a):
	global counter
	n = len(a) // 2
	if a[0] > a[n]:
		a = a[n:] + a[:n]
		counter += 1
	return a

def repeat(a):
	global counter
	if len(a) == 1:
		return a
	a = flip(a)
	n = len(a) // 2
	return repeat(a[:n]) + repeat(a[n:])
for _ in range(int(input())):
	m = int(input())
	p = list(map(int, input().split()))
	a = list(range(1, m + 1))
	counter = 0
	p = repeat(p)
	if p != a:
		print(-1)
	else:
		print(counter)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	logn = int(math.log2(n))
	a = [int(x) for x in input().split()]
	res = 0
	flag = True
	for i in range(1, logn + 1):
		l = int(2 ** i)
		for idx in range(0, n, l):
			l_large = a[idx + l // 2 - 1]
			l_small = a[idx]
			r_small = a[idx + l // 2]
			r_large = a[idx + l - 1]
			if abs(r_small - l_large) > 1 and abs(r_large - l_small) > 1:
				flag = False
				break
			elif l_small > r_large:
				res += 1
				(a[idx:idx + l // 2], a[idx + l // 2:idx + l]) = (a[idx + l // 2:idx + l], a[idx:idx + l // 2])
		if not flag:
			break
	if not flag:
		print('-1')
	else:
		print(res)


t = int(input())

class Solution:

	def __init__(self):
		self.operations = 0

	def findOperations(self, array):
		if len(array) == 1:
			return array
		mid = len(array) // 2
		left = self.findOperations(array[:mid])
		right = self.findOperations(array[mid:])
		if left[0] > right[0]:
			self.operations += 1
			return right + left
		return left + right
solution = Solution()
for _ in range(t):
	m = int(input())
	permutations = list(map(int, input().split()))
	resultPermutations = solution.findOperations(permutations)
	left = 0
	right = 1
	while right < len(resultPermutations):
		if resultPermutations[right] - resultPermutations[left] != 1:
			print(-1)
			break
		left += 1
		right += 1
	else:
		print(solution.operations)
	solution.operations = 0


T = int(input())
while T:
	T -= 1
	v = []
	for i in range(20):
		v.append([])
	n = int(input())
	v[0] = [*map(int, input().split())]
	ans = 0
	k = 0
	flag = 1
	while len(v[k]) != 1:
		for i in range(0, len(v[k]), 2):
			dis = 0
			if v[k][i] > v[k][i + 1]:
				ans += 1
				dis = v[k][i] - v[k][i + 1]
			else:
				dis = v[k][i + 1] - v[k][i]
			if dis != 4 ** k:
				flag = 0
				break
			v[k + 1].append(v[k][i] + v[k][i + 1])
		if flag == 0:
			break
		k = k + 1
	if flag:
		print(ans)
	else:
		print('-1')


import math
import collections
import bisect
import heapq
from collections import deque
from math import sqrt, ceil, floor

def inp_arr():
	return list(map(int, input().strip().split(' ')))

def inp_int():
	return int(input())

def inp_str():
	return input()

def solve():
	(n,) = inp_arr()
	a = inp_arr()
	block = 2
	ans = 0
	while block <= n:
		half = block // 2
		for i in range(0, n, block):
			if a[i:i + block] != sorted(a[i:i + block]):
				ans += 1
				a[i:i + block] = sorted(a[i:i + block])
				if a[i + block - 1] - a[i] != block - 1:
					print(-1)
					return
			elif a[i + block - 1] - a[i] != block - 1:
				print(-1)
				return
		block = block * 2
	print(ans)
tt = inp_int()
for t in range(tt):
	solve()


cases = int(input())

def checkrecur(leftList, rightList, diff):
	nextLength = diff // 2
	l = min(leftList)
	r = min(rightList)
	if abs(l - r) == diff:
		if nextLength > 0:
			t1 = checkrecur(leftList[:nextLength], leftList[nextLength:], nextLength)
			t2 = checkrecur(rightList[:nextLength], rightList[nextLength:], nextLength)
			if t1 == -1 or t2 == -1:
				return -1
			if l < r:
				return t1 + t2
			else:
				return 1 + t1 + t2
		elif l < r:
			return 0
		else:
			return 1
	else:
		return -1
for i in range(cases):
	m = int(input())
	ord = input().split()
	if m == 1:
		print('0')
		continue
	order = [int(j) for j in ord]
	diff = m // 2
	print(checkrecur(order[:diff], order[diff:], diff))


def cal(n, arr):
	if n == 1:
		return 0
	if n == 2:
		if arr[0] == arr[1] + 1:
			return 1
		elif arr[0] == arr[1] - 1:
			return 0
		else:
			return -1
	aa = sum(arr[:n // 2])
	bb = sum(arr[n // 2:])
	if aa > bb:
		if aa - bb == (n // 2) ** 2:
			k1 = cal(n // 2, arr[:n // 2])
			k2 = cal(n // 2, arr[n // 2:])
			if k1 == -1 or k2 == -1:
				return -1
			else:
				return k1 + k2 + 1
		else:
			return -1
	elif bb - aa == (n // 2) ** 2:
		k1 = cal(n // 2, arr[:n // 2])
		k2 = cal(n // 2, arr[n // 2:])
		if k1 == -1 or k2 == -1:
			return -1
		else:
			return k1 + k2
	else:
		return -1
for jj in range(int(input())):
	m = int(input())
	k = [int(i) for i in input().split()]
	print(cal(m, k))