You have a permutation: an array $a = [a_1, a_2, \ldots, a_n]$ of distinct integers from $1$ to $n$. The length of the permutation $n$ is odd.

Consider the following algorithm of sorting the permutation in increasing order.

A helper procedure of the algorithm, $f(i)$, takes a single argument $i$ ($1 \le i \le n-1$) and does the following. If $a_i > a_{i+1}$, the values of $a_i$ and $a_{i+1}$ are exchanged. Otherwise, the permutation doesn't change.

The algorithm consists of iterations, numbered with consecutive integers starting with $1$. On the $i$-th iteration, the algorithm does the following:

if $i$ is odd, call $f(1), f(3), \ldots, f(n - 2)$;

if $i$ is even, call $f(2), f(4), \ldots, f(n - 1)$.

It can be proven that after a finite number of iterations the permutation will be sorted in increasing order.

After how many iterations will this happen for the first time?


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($3 \le n \le 999$; $n$ is odd) — the length of the permutation.

The second line contains $n$ distinct integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the permutation itself.

It is guaranteed that the sum of $n$ over all test cases does not exceed $999$.


-----Output-----

For each test case print the number of iterations after which the permutation will become sorted in increasing order for the first time.

If the given permutation is already sorted, print $0$.


-----Examples-----

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


-----Note-----

In the first test case, the permutation will be changing as follows:

after the $1$-st iteration: $[2, 3, 1]$;

after the $2$-nd iteration: $[2, 1, 3]$;

after the $3$-rd iteration: $[1, 2, 3]$.

In the second test case, the permutation will be changing as follows:

after the $1$-st iteration: $[4, 5, 1, 7, 2, 3, 6]$;

after the $2$-nd iteration: $[4, 1, 5, 2, 7, 3, 6]$;

after the $3$-rd iteration: $[1, 4, 2, 5, 3, 7, 6]$;

after the $4$-th iteration: $[1, 2, 4, 3, 5, 6, 7]$;

after the $5$-th iteration: $[1, 2, 3, 4, 5, 6, 7]$.

In the third test case, the permutation is already sorted and the answer is $0$.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Implementation

Complete search


Solutions:
t = int(input())
for _ in range(t):
	n = int(input())
	inp = input().split()
	nums = [int(i) for i in inp]
	step = 0
	while nums != sorted(nums):
		for i in range(step % 2, n - 1, 2):
			if nums[i] > nums[i + 1]:
				(nums[i], nums[i + 1]) = (nums[i + 1], nums[i])
				f = 1
		step += 1
	print(step)


import os
import sys
from io import BytesIO, IOBase
from bisect import bisect_right, insort_right
BUFSIZE = 8192
import array

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
getint = lambda : int(sys.stdin.readline().rstrip('\r\n'))
getints = lambda : map(int, sys.stdin.readline().rstrip('\r\n').split())
lgetints = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
getstrs = lambda : map(str, sys.stdin.readline().rstrip('\r\n').split())

def prog_name():
	n = getint()
	l = lgetints()
	cnt = 0
	while l != sorted(l):
		cnt += 1
		if cnt & 1:
			for x in range(n - 1):
				if not x & 1:
					if l[x] > l[x + 1]:
						temp = l[x]
						l[x] = l[x + 1]
						l[x + 1] = temp
		else:
			for x in range(n - 1):
				if x & 1:
					if l[x] > l[x + 1]:
						temp = l[x]
						l[x] = l[x + 1]
						l[x + 1] = temp
	print(cnt)

def main():
	T = getint()
	for unique in range(T):
		prog_name()
main()


def solve(p, A):
	i = 1
	sorted_A = sorted(A)
	while A != sorted_A:
		if i % 2 == 1:
			for j in range(0, p - 2, 2):
				if A[j] > A[j + 1]:
					(A[j], A[j + 1]) = (A[j + 1], A[j])
		else:
			for j in range(1, p - 1, 2):
				if A[j] > A[j + 1]:
					(A[j], A[j + 1]) = (A[j + 1], A[j])
		i += 1
	return i - 1

def main():
	ans = []
	t = int(input())
	for _ in range(t):
		p = int(input())
		A = list(map(int, input().split(' ')))
		ans.append(solve(p, A))
	for a in ans:
		print(a)
main()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	x = sorted(a)
	ans = 0
	while x != a:
		ans += 1
		if ans % 2:
			for i in range(0, n, 2):
				if i + 1 < n and a[i] > a[i + 1]:
					(a[i], a[i + 1]) = (a[i + 1], a[i])
		else:
			for i in range(1, n, 2):
				if i + 1 < n and a[i] > a[i + 1]:
					(a[i], a[i + 1]) = (a[i + 1], a[i])
	print(ans)


t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	temp = sorted(a)
	count = 0
	flag = 0
	j = 1
	while a != temp:
		if j % 2:
			k = 0
			while k < n - 1:
				if a[k] > a[k + 1]:
					x = a[k]
					a[k] = a[k + 1]
					a[k + 1] = x
				k += 2
		else:
			k = 1
			while k < n - 1:
				if a[k] > a[k + 1]:
					x = a[k]
					a[k] = a[k + 1]
					a[k + 1] = x
				k += 2
		count += 1
		j += 1
	print(count)


def cast(cre, typ):
	return type(typ)(map(cre, typ))

def inp_lis(cre):
	if cre == str:
		return input().split()
	elif cre == bool:
		return cast(bool, cast(int, input().split()))
	else:
		return cast(cre, input().split())

def repl(str_, idx=-1, char=''):
	leng = len(str_)
	return str_[:idx] + char + str_[(leng + idx) % leng + 1:]

def sort_(seq, idx):
	if seq[idx] > seq[idx + 1]:
		tmp = seq[idx]
		seq[idx] = seq[idx + 1]
		seq[idx + 1] = tmp
	return

def issort_(seq):
	last = 0
	for e in seq:
		if last > e:
			return False
		else:
			last = e
	else:
		return True

def solution():
	for t in range(int(input())):
		n = int(input())
		per = inp_lis(int)
		idx = 1
		while True:
			if idx % 2 == 1:
				if issort_(per):
					idx -= 1
					break
				for i in range(1, n - 1, 2):
					sort_(per, i - 1)
			else:
				if issort_(per):
					idx -= 1
					break
				for i in range(2, n, 2):
					sort_(per, i - 1)
			idx += 1
		print(idx)
	return
solution()


def arr_is_sorted(a):
	for i in range(len(a) - 1):
		if a[i] > a[i + 1]:
			return False
	return True
for _ in range(int(input())):
	n = int(input())
	arr = [-1] + list(map(int, input().split()))
	res = 0
	i = 1
	while True:
		if arr_is_sorted(arr):
			print(res)
			break
		else:
			res += 1
		if i % 2 == 0:
			for j in range(2, n, 2):
				if arr[j] > arr[j + 1]:
					(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
		else:
			for j in range(1, n - 1, 2):
				if arr[j] > arr[j + 1]:
					(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
		i += 1


t = int(input())

def odd(a, n):
	for i in range(0, n - 1, 2):
		if a[i] > a[i + 1]:
			tmp = a[i]
			a[i] = a[i + 1]
			a[i + 1] = tmp
	return a

def even(a, n):
	for i in range(1, n - 1, 2):
		if a[i] > a[i + 1]:
			tmp = a[i]
			a[i] = a[i + 1]
			a[i + 1] = tmp
	return a
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	ans = 0
	while b != a:
		if ans % 2 == 0:
			a = odd(a, n)
		else:
			a = even(a, n)
		ans += 1
	print(ans)


import sys
import math

def f(a, i):
	if a[i] > a[i + 1]:
		t = a[i]
		a[i] = a[i + 1]
		a[i + 1] = t

def is_increasing(a):
	for i in range(len(a) - 1):
		if a[i] > a[i + 1]:
			return False
	return True
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	line = []
	line = [int(i) for i in sys.stdin.readline().split()]
	step = 1
	while not is_increasing(line):
		if step % 2 == 1:
			for i in range(0, n - 1, 2):
				f(line, i)
		else:
			for i in range(1, n - 1, 2):
				f(line, i)
		step += 1
	print(step - 1)


for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	sorted_array = sorted(array)
	if array == sorted_array:
		print(0)
	else:
		count = 0
		for i in range(n):
			if i == 0 or not i & 1:
				for j in range(0, n - 1, 2):
					if array[j] > array[j + 1]:
						(array[j], array[j + 1]) = (array[j + 1], array[j])
			else:
				for j in range(1, n - 1, 2):
					if array[j] > array[j + 1]:
						(array[j], array[j + 1]) = (array[j + 1], array[j])
			count = i
			if array == sorted_array:
				break
		print(count + 1)


t = int(input())
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	sorted_nums = sorted(nums)
	res = 0
	while nums != sorted_nums:
		res += 1
		if res % 2 == 0:
			seq = range(1, n - 1, 2)
		else:
			seq = range(0, n - 1, 2)
		for i in seq:
			if nums[i] > nums[i + 1]:
				(nums[i], nums[i + 1]) = (nums[i + 1], nums[i])
	print(res)


def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		iter = 0
		a_out = a
		while True:
			if issorted(a_out):
				break
			iter += 1
			a_out = ssort(a, iter)
		print(iter)

def issorted(a):
	for i in range(len(a) - 1):
		if a[i] > a[i + 1]:
			return False
	return True

def ssort(a, i):
	n = len(a)
	if i % 2 == 0:
		for i in range(1, n - 1, 2):
			if a[i + 1] < a[i]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
	else:
		for i in range(0, n - 2, 2):
			if a[i + 1] < a[i]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
	return a
main()


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	e = list(range(1, n + 1))
	ans = 0
	while a != e:
		for j in range(ans % 2, n - 1, 2):
			if a[j] > a[j + 1]:
				(a[j], a[j + 1]) = (a[j + 1], a[j])
		ans += 1
	print(ans)


def bs(a, f):
	k = 0
	if f:
		k = 1
	for j in range(k, len(a) - 1, 2):
		if a[j] > a[j + 1] and j + 1 < len(a):
			(a[j], a[j + 1]) = (a[j + 1], a[j])
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	l = a.copy()
	l.sort()
	for i in range(0, n):
		if l == a:
			break
		bs(a, i % 2)
		ans += 1
	print(ans)


n = int(input())
for i in range(n):
	l = []
	m = int(input())
	k = input()
	k = k.split()
	for o in k:
		l.append(int(o))
	t = True
	zaehler = 0
	s = -1
	z = 0
	while t:
		t = False
		s = -1
		for x in range(len(l) - 1):
			if l[x] > l[x + 1]:
				t = True
		if t == False:
			break
		if z % 2 == 0:
			for x in range(0, len(l) - 1, 2):
				if l[x] > l[x + 1] and l[x] != s:
					s = l[x]
					del l[x]
					l.insert(x + 1, s)
		else:
			for x in range(1, len(l) - 1, 2):
				if l[x] > l[x + 1] and l[x] != s:
					s = l[x]
					del l[x]
					l.insert(x + 1, s)
		zaehler += 1
		z += 1
	print(zaehler)


f = sorted
for s in [*open(0)][2::2]:
	(*a,) = map(int, s.split())
	i = c = 0
	while a > f(a):
		j = i
		while j < len(a) - 1:
			a[j:j + 2] = f(a[j:j + 2])
			j += 2
		c += 1
		i ^= 1
	print(c)


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	alist = [int(i) for i in input().strip().split(' ')]
	alist_sorted = alist[:]
	alist_sorted.sort()
	swap_round = 0
	while True:
		if alist == alist_sorted:
			break
		for i in range(0, n - 1, 2):
			if alist[i] > alist[i + 1]:
				(alist[i], alist[i + 1]) = (alist[i + 1], alist[i])
		swap_round += 1
		if alist == alist_sorted:
			break
		for i in range(1, n - 1, 2):
			if alist[i] > alist[i + 1]:
				(alist[i], alist[i + 1]) = (alist[i + 1], alist[i])
		swap_round += 1
		if alist == alist_sorted:
			break
	print(swap_round)


t = int(input())

def fun():
	global c, l
	for i in range(n):
		x = (i + 1) % 2
		for j in range(n):
			try:
				if (j + 1) % 2 == x and l[j] > l[j + 1]:
					(l[j], l[j + 1]) = (l[j + 1], l[j])
			except:
				pass
		c += 1
		if l == y:
			return True
	return l == y
for r in range(t):
	n = int(input())
	l = [int(a) for a in input().split()]
	c = 0
	y = l[:]
	y.sort()
	f = 1
	while l != y:
		fun()
	print(c)


t = int(input())
while t:
	n = int(input())
	A = list(map(int, input().split()))[:n]
	Abar = A.copy()
	Abar.sort()
	ans = 0
	while Abar != A:
		for i in range(ans % 2, n - 1, 2):
			if A[i] > A[i + 1]:
				(A[i], A[i + 1]) = (A[i + 1], A[i])
		ans += 1
	print(ans)
	t -= 1


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

def is_sorted(a):
	return all((a[i] < a[i + 1] for i in range(len(a) - 1)))
t = int(input())
for ti in range(t):
	n = int(input())
	a = read()
	ans = 0
	while not is_sorted(a):
		for i in range(ans % 2, n - 1, 2):
			if a[i] > a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
		ans += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	sa = sorted(a)
	j = 0
	while a != sa:
		if (j + 1) % 2:
			for k in range(0, n - 2, 2):
				if a[k] > a[k + 1]:
					(a[k], a[k + 1]) = (a[k + 1], a[k])
		else:
			for k in range(1, n - 1, 2):
				if a[k] > a[k + 1]:
					(a[k], a[k + 1]) = (a[k + 1], a[k])
		j += 1
	print(j)


import sys
import math
import bisect
t = int(input())
for a0 in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	l1 = l.copy()
	l1.sort()
	if l1 == l:
		print(0)
	else:
		c = 0
		i1 = 0
		while l1 != l:
			c += 1
			if i1 % 2 == 0:
				for i in range(0, len(l) - 1, 2):
					if l[i] > l[i + 1]:
						temp = l[i + 1]
						l[i + 1] = l[i]
						l[i] = temp
				i1 = 1
			else:
				i1 = 0
				for i in range(1, len(l), 2):
					if l[i] > l[i + 1]:
						temp = l[i + 1]
						l[i + 1] = l[i]
						l[i] = temp
		print(c)


n = int(input())
for i in range(n):
	length = int(input())
	permutation = [int(x) for x in input().split()]
	(count, order) = (0, 0)
	solution = sorted(permutation)
	if permutation == solution:
		print(0)
	else:
		for j in range(1, length + 1):
			if j % 2 == 0:
				order = 1
				while order < length:
					if permutation[order] > permutation[order + 1]:
						(permutation[order], permutation[order + 1]) = (permutation[order + 1], permutation[order])
					order += 2
			elif j % 2 != 0:
				order = 0
				while order < length - 1:
					if permutation[order] > permutation[order + 1]:
						(permutation[order], permutation[order + 1]) = (permutation[order + 1], permutation[order])
					order += 2
			count += 1
			if permutation == solution:
				print(count)
				break


for i in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	s = str(sorted(a))
	for i in range(n + 1000):
		if str(a) == s:
			print(i)
			break
		else:
			for i in range(i % 2, n - 1, 2):
				if a[i] > a[i + 1]:
					(a[i], a[i + 1]) = (a[i + 1], a[i])


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	cnt = 0
	i = 1
	b = sorted(a)
	while a != b:
		if i % 2 != 0:
			for j in range(0, n - 2, 2):
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		else:
			for j in range(1, n - 1, 2):
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		i = i + 1
	print(i - 1)
	t = t - 1


def foo(arr, i):
	if arr[i - 1] > arr[i]:
		(arr[i - 1], arr[i]) = (arr[i], arr[i - 1])

def manyFoo(arr, start, end, step):
	for i in range(start, end, step):
		foo(arr, i)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	sortArr = sorted(arr)
	step = 0
	while arr != sortArr:
		step += 1
		if step % 2 == 0:
			manyFoo(arr, 2, n, 2)
		else:
			manyFoo(arr, 1, n - 1, 2)
	print(step)


t = int(input())
for _ in range(t):
	l = int(input())
	per = list(map(int, input().split()))
	temp = sorted(per)
	for i in range(1, l + 1):
		if temp == per:
			i -= 1
			break
		if i % 2 != 0:
			for j in range(0, l - 1, 2):
				if per[j] > per[j + 1]:
					(per[j], per[j + 1]) = (per[j + 1], per[j])
		else:
			for j in range(1, l - 1, 2):
				if per[j] > per[j + 1]:
					(per[j], per[j + 1]) = (per[j + 1], per[j])
	print(i)


def fun(arr, n):

	def is_sorted(nums, n):
		for i in range(n - 1):
			if nums[i] > nums[i + 1]:
				return False
		return True
	count = 0
	while not is_sorted(arr, n):
		i = count % 2
		while i < n - 1:
			if arr[i] > arr[i + 1]:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			i += 2
		count += 1
	return count
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(fun(arr, n))


from collections import Counter
from itertools import accumulate, product, groupby
import operator
import math

def solve():
	n = int(input())
	arr = [-1] + [int(char) for char in input().split()]
	n += 1

	def odd_sort():
		something_changed = False
		for i in range(1, n - 1, 2):
			if arr[i] > arr[i + 1]:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
				something_changed = True
		return something_changed

	def even_sort():
		something_changed = False
		for i in range(2, n, 2):
			if arr[i] > arr[i + 1]:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
				something_changed = True
		return something_changed
	(prev_changed, cur_is_odd) = (True, True)
	ans = 0
	while True:
		if cur_is_odd:
			cur_changed = odd_sort()
		else:
			cur_changed = even_sort()
		cur_is_odd = not cur_is_odd
		if not prev_changed and (not cur_changed):
			break
		ans += 1
		prev_changed = cur_changed
	return ans - 1
for _ in range(int(input())):
	print(solve())


def odd(n, a):
	for i in range(0, n - 1, 2):
		if a[i] > a[i + 1]:
			z = a[i]
			a[i] = a[i + 1]
			a[i + 1] = z
	return a

def even(n, a):
	for i in range(1, n, 2):
		if a[i] > a[i + 1]:
			z = a[i]
			a[i] = a[i + 1]
			a[i + 1] = z
	return a
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	i = 0
	while a != b:
		if i % 2 != 0:
			even(n, a)
		else:
			odd(n, a)
		i += 1
	print(i)


def count_iterations(n, a):
	iter = 0
	s_copy = []
	s_copy = list(a)
	s_copy.sort()
	while a != s_copy:
		if iter % 2 == 0:
			for j in range(0, n - 1, 2):
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		else:
			for j in range(1, n - 1, 2):
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		iter += 1
	return iter
t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().rstrip().split()))
	response = count_iterations(n, a)
	print(f'{response}')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	l1 = sorted(l)
	a = 0
	while l != l1:
		flag = False
		for j in range(a % 2, n - 1, 2):
			if l[j] > l[j + 1]:
				(l[j], l[j + 1]) = (l[j + 1], l[j])
		a += 1
	print(a)


t = int(input())

def check():
	for i in range(1, n + 1):
		if a[i] != i:
			return False
	return True

def change(i):
	if i % 2 == 1:
		for j in range(1, n - 1, 2):
			if a[j] > a[j + 1]:
				(a[j], a[j + 1]) = (a[j + 1], a[j])
	else:
		for j in range(2, n, 2):
			if a[j] > a[j + 1]:
				(a[j], a[j + 1]) = (a[j + 1], a[j])
for _ in range(t):
	n = int(input())
	N = n + 5
	a = [-1] * N
	a[1:n + 1] = map(int, input().split())
	ans = 0
	for i in range(1, n * n + 1):
		if check():
			print(i - 1)
			break
		else:
			change(i)


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	ans = 0
	for i in range(n - 1):
		if x[i + 1] != x[i] + 1:
			ans = 1
			break
	if ans == 0:
		print(ans)
		continue
	else:
		while x != list(range(1, n + 1)):
			if ans % 2 == 1:
				for i in range(0, n - 1, 2):
					if x[i] > x[i + 1]:
						(x[i], x[i + 1]) = (x[i + 1], x[i])
			elif ans % 2 == 0:
				for j in range(1, n - 1, 2):
					if x[j] > x[j + 1]:
						(x[j], x[j + 1]) = (x[j + 1], x[j])
			ans += 1
		if ans == 1:
			print(1)
		else:
			print(ans - 1)


t = int(input())
for test in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	i = 0
	check = 1
	while check:
		i += 1
		check = 0
		for k in range(n - 1):
			if a[k] > a[k + 1]:
				check = 1
				if (k + 1) % 2 == i % 2:
					(a[k], a[k + 1]) = (a[k + 1], a[k])
	print(i - 1)


import os, sys
from io import BytesIO, IOBase

def sorteddd(arr):
	for i in range(len(arr)):
		if arr[i] != i + 1:
			return False
	return True

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		i = 0
		while not sorteddd(arr):
			i += 1
			for idx in range(n):
				if idx % 2 != i % 2 and idx != n - 1 and (arr[idx] > arr[idx + 1]):
					(arr[idx], arr[idx + 1]) = (arr[idx + 1], arr[idx])
		print(i)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = 0
	s = sorted(a)
	while a != s and cnt < n:
		for i in range(cnt % 2, n - 1, 2):
			if a[i] > a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
		cnt += 1
	print(cnt)


def strangeSort(ar, n):
	sortedAry = sorted(ar)
	count = 0
	for i in range(n):
		if ar == sortedAry:
			return count
		count += 1
		if (i + 1) % 2 == 0:
			for j in range(1, n - 1, 2):
				if ar == sortedAry:
					return count
				if ar[j] > ar[j + 1]:
					(ar[j], ar[j + 1]) = (ar[j + 1], ar[j])
		else:
			for k in range(0, n - 2, 2):
				if ar == sortedAry:
					return count
				if ar[k] > ar[k + 1]:
					(ar[k], ar[k + 1]) = (ar[k + 1], ar[k])
	return count
t = int(input())
for _ in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	print(strangeSort(ar, n))


import os
import sys
from io import BytesIO, IOBase
import math
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	input = lambda : sys.stdin.readline().rstrip('\r\n')

def f(i):
	if a[i] > a[i + 1]:
		(a[i], a[i + 1]) = (a[i + 1], a[i])
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	if a == b:
		print(0)
		continue
	ans = 0
	i = 1
	while True:
		done = True
		for x in range(n):
			if a[x] != b[x]:
				done = False
		if done:
			break
		if i % 2 == 0:
			for j in range(1, n - 1, 2):
				f(j)
		else:
			for j in range(0, n - 2, 2):
				f(j)
		ans += 1
		i += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = arr[:]
	d = sorted(d)
	ans = 0
	print
	while d != arr:
		for i in range(ans % 2, n - 1, 2):
			if arr[i] > arr[i + 1]:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		ans += 1
	print(ans)


from itertools import combinations, permutations
from sys import path_hooks, stdin, stdout
from collections import Counter, deque
import math
from copy import deepcopy
import random
import heapq
import sys
sys.setrecursionlimit(10 ** 5)

def mapinput():
	return map(int, stdin.readline().split())

def strinput():
	return stdin.readline().strip()

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

def intinput():
	return int(stdin.readline().strip())

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	ans = []
	for p in range(n + 1):
		if prime[p]:
			ans.append(p)
	return ans
coprime1 = {6: 100003, 5: 10007, 4: 1009, 3: 101, 2: 11, 1: 2, 7: 1000003, 8: 10000019, 9: 100000007}
coprime2 = {8: 10000169, 9: 100000049, 7: 1000033, 6: 100019, 5: 10009, 4: 1013, 3: 103, 2: 13, 1: 3}

def writ(ss):
	stdout.write(str(ss) + '\n')
mod = 998244353

def sumn(n):
	return n * (n + 1) // 2

def perm(lis):
	if len(lis) < 2:
		return lis
	anss = []
	for i in range(len(lis)):
		ele = lis[i]
		liss = lis[:i] + lis[i + 1:]
		for j in perm(liss):
			anss.append(ele + j)
	return anss
for test in range(intinput()):

	def solve():
		n = intinput()
		arr = listinput()
		ar = sorted(arr)
		ans = 0
		if arr == ar:
			return 0
		while arr != ar:
			ans += 1

			def hihi(f):
				for i in range(1 - f, n - 1 - f, 2):
					if arr[i] > arr[i + 1]:
						(arr[i + 1], arr[i]) = (arr[i], arr[i + 1])
			hihi(ans % 2)
		return ans
	print(solve())


def solution():
	for _ in range(int(input())):
		n = int(input())
		a = [int(x) for x in input().split()]
		c = 0
		b = sorted(a)
		if a == b:
			print(0)
			continue
		i = 0
		while a != b:
			d = 0
			if i % 2 == 0:
				for j in range(0, n - 2, 2):
					if a[j] > a[j + 1]:
						(a[j], a[j + 1]) = (a[j + 1], a[j])
			else:
				for j in range(1, n - 1, 2):
					if a[j] > a[j + 1]:
						(a[j], a[j + 1]) = (a[j + 1], a[j])
			c += 1
			i += 1
		print(c)
solution()


def main():
	test = int(input())
	for _ in range(test):
		n = int(input())
		a = list(map(int, input().split()))
		tar = [i for i in range(1, n + 1)]
		ans = 0
		if a == tar:
			print(ans)
			continue
		i = 0
		while True:
			st = 0 if i % 2 == 0 else 1
			for j in range(n):
				if j % 2 == st and j + 1 < n and (a[j] > a[j + 1]):
					(a[j], a[j + 1]) = (a[j + 1], a[j])
			ans += 1
			if a == tar:
				print(ans)
				break
			i += 1
	return
main()


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
depth = 1000005
mod = 1000000007
lim = mod * mod
sys.setrecursionlimit(depth)
from math import inf, ceil, sqrt
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(s, c) = (sorted(a), 0)
	while a != s:
		c += 1
		if c & 1:
			for i in range(0, n - 2, 2):
				if a[i] > a[i + 1]:
					(a[i], a[i + 1]) = (a[i + 1], a[i])
		else:
			for i in range(1, n - 1, 2):
				if a[i] > a[i + 1]:
					(a[i], a[i + 1]) = (a[i + 1], a[i])
	print(c)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	t = sorted(l)
	c = 0
	for i in range(n):
		while t != l:
			if (c + 1) % 2 == 1:
				for i in range(n - 1):
					if (i + 1) % 2 == 1 and l[i] > l[i + 1]:
						(l[i], l[i + 1]) = (l[i + 1], l[i])
			else:
				for i in range(n - 1):
					if (i + 1) % 2 == 0 and l[i] > l[i + 1]:
						(l[i], l[i + 1]) = (l[i + 1], l[i])
			c = c + 1
	print(c)


import math
from collections import Counter, defaultdict
import sys
mod = 10 ** 9 + 7
input = sys.stdin.readline
readInt = lambda : int(input().strip())
readfloat = lambda : float(input().strip())
readStr = lambda : input().strip()
intList = lambda : list(map(int, input().strip().split()))
intMap = lambda : map(int, input().strip().split())
floatList = lambda : list(map(float, input().strip().split()))
floatMap = lambda : map(float, input().strip().split())
strList = lambda : list(input().strip().split())

def print(*args, end='\n', sep=' '):
	for i in args:
		sys.stdout.write(str(i))
		sys.stdout.write(sep)
	sys.stdout.write(end)

def solve():
	brr = sorted(arr)
	res = 0
	while True:
		if arr == brr:
			return res
		for i in range(res % 2, n - 1, 2):
			if arr[i] > arr[i + 1]:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		res += 1
for _ in range(readInt()):
	n = readInt()
	arr = intList()
	print(solve())


t = int(input())
while t:
	size = int(input())
	arr = [int(i) for i in input().split()]
	flag = True
	count = 0
	con = 0
	switch = False
	while flag:
		if switch:
			i = 1
		else:
			i = 0
		switch = not switch
		while i < size - 1:
			if arr[i] > arr[i + 1]:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
				flag = False
			i += 2
		if flag == False:
			count += con + 1
			con = 0
			flag = True
		else:
			con += 1
			if con == 2:
				flag = False
	print(count)
	t -= 1


def funod(n):
	for i in range(0, len(n) - 2, 2):
		if n[i] > n[i + 1]:
			(n[i], n[i + 1]) = (n[i + 1], n[i])
	return n

def funeve(n):
	for i in range(1, len(n) - 1, 2):
		if n[i] > n[i + 1]:
			(n[i], n[i + 1]) = (n[i + 1], n[i])
	return n
flag = 1
coount = 0
w = int(input())
for i in range(w):
	k = int(input())
	t = list(map(int, input().split()))
	b = list(t)
	b.sort()
	while t != b:
		if flag % 2 == 0:
			t = funeve(t)
			flag += 1
			coount += 1
		else:
			t = funod(t)
			flag += 1
			coount += 1
	print(coount)
	coount = 0
	flag = 1


import sys
input = lambda : sys.stdin.readline().strip()

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	res = 0
	brr = sorted(arr)
	p = 1
	while arr != brr:
		if p:
			for i in range(0, n, 2):
				arr[i:i + 2] = sorted(arr[i:i + 2])
		else:
			for i in range(1, n, 2):
				arr[i:i + 2] = sorted(arr[i:i + 2])
		p ^= 1
		res += 1
	return res
for _ in range(int(input())):
	print(solve())


def func(n, a):
	(iteration, i) = (0, 0)
	sort = sorted(a)
	while a != sort:
		if iteration % 2 == 0:
			i = 0
			for j in range(i, n - 1, 2):
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		else:
			i = 1
			for j in range(i, n, 2):
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		iteration += 1
	return iteration
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(func(n, a))


test = int(input())

def f(i):
	a = list[i - 1]
	b = list[i]
	if a > b:
		list[i - 1] = b
		list[i] = a
		return list
	else:
		return list

def iteration():
	iter = 1
	true_list = [0] * n
	for y in range(n):
		true_list[y] = y + 1
	while list != true_list:
		if iter % 2 == 1:
			for num in range(1, n - 1, 2):
				f(num)
		if iter % 2 == 0:
			for num in range(2, n, 2):
				f(num)
		iter += 1
	return iter - 1
for case in range(test):
	n = int(input())
	list = input().split()
	list = [int(x) for x in list]
	print(iteration())


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	sort = sorted(a)
	if a == sort:
		print(0)
	else:
		count = 0
		while a != sort:
			if count % 2 == 0:
				for i in range(0, n - 1, 2):
					if a[i + 1] < a[i]:
						(a[i + 1], a[i]) = (a[i], a[i + 1])
			else:
				for i in range(1, n - 1, 2):
					if a[i + 1] < a[i]:
						(a[i], a[i + 1]) = (a[i + 1], a[i])
			count = count + 1
		print(count)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	s = [i for i in arr]
	s.sort()
	ans = 0
	i = 1
	while arr != s:
		if i % 2:
			j = 1
			while j <= n - 2:
				if arr[j - 1] > arr[j]:
					(arr[j - 1], arr[j]) = (arr[j], arr[j - 1])
				j += 2
		else:
			j = 2
			while j <= n - 1:
				if arr[j - 1] > arr[j]:
					(arr[j], arr[j - 1]) = (arr[j - 1], arr[j])
				j += 2
		i += 1
		ans += 1
	print(ans)


def solve():
	input()
	a = list(map(int, input().split()))
	i = 0
	while True:
		if a == sorted(a):
			print(i)
			break
		if i % 2 == 0:
			for j in range(0, len(a) - 2, 2):
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		else:
			for j in range(1, len(a) - 1, 2):
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		i += 1
for i in range(int(input())):
	solve()


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	b = sorted(a)
	c = 0
	while a != b:
		if c % 2 == 0:
			for j in range(0, n - 1, 2):
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		else:
			for j in range(1, n - 1, 2):
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		ans += 1
		c += 1
	print(ans)


from math import ceil

def map_input(type=1):
	if type == 1:
		return map(int, input().split())
	elif type == 2:
		return map(float, input().split())
	elif type == 3:
		return map(str, input().split())
	return None

def list_input(type=1):
	return list(map_input(type))

def give_excel_column_name(r: int):
	l = 1
	r -= 1
	ans: str = ''
	while 26 ** l <= r:
		r -= 26 ** l
		l += 1
	while l > 0:
		ans += chr(ord('A') + r // 26 ** (l - 1) % 26)
		l -= 1
	return ans

def give_excel_column_number(name: str):
	p = 1
	ans: int = 0
	for j in range(len(name)):
		ans = ans + p * (ord(name[j]) - ord('A') + 1)
		p = p * 26
	return ans

def sorted_indices(s):
	li = []
	for i in range(len(s)):
		li.append([s[i], i])
	li.sort()
	return [x[1] for x in li]

def floorSearch(arr, x, low=-1, high=-1):
	if low == -1:
		low = 0
	if high == -1:
		high == len(arr) - 1
	if low > high:
		return -1
	if x >= arr[high]:
		return high
	mid = int((low + high) / 2)
	if arr[mid] == x:
		return mid
	if mid > 0 and arr[mid - 1] <= x and (x < arr[mid]):
		return mid - 1
	if x < arr[mid]:
		return floorSearch(arr, low, mid - 1, x)
	return floorSearch(arr, mid + 1, high, x)

def find_index(arr, x):
	low = 0
	high = len(arr) - 1
	mid = 0
	while low <= high:
		mid = (high + low) // 2
		if arr[mid] < x:
			low = mid + 1
		elif arr[mid] > x:
			high = mid - 1
		else:
			return mid
	return -1

def floyd_warshell(g):
	n = len(g)
	d = g.copy()
	for k in range(n):
		for i in range(n):
			for j in range(n):
				d[i][j] = min(d[i][j], d[i][k] + d[k][j])
	return d

def int_input(type=1):
	if type == 1:
		return int(input())
	elif type == 2:
		return float(int(input()))

def range_input():
	return range(int_input())

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def is_prime(n):
	if n < 2:
		return False
	if n == 2:
		return True
	for i in range(2, int(n / 2) + 1):
		if n % i == 0:
			return False
	return True

def main():
	for _ in range_input():
		n = int_input()
		l = list_input()
		s = sorted(l)
		ans = 0
		i = 0
		while s != l:
			for j in range(i % 2, n - 1, 2):
				if l[j] > l[j + 1]:
					(l[j], l[j + 1]) = (l[j + 1], l[j])
			i += 1
		print(i)
try:
	main()
except:
	pass


n_t = int(input())

def swap(j, k):
	tmp = j
	j = k
	k = tmp
	return (j, k)

def strange_sort(nums):
	sorted_arr = sorted(nums)
	n = len(nums)
	num_of_it = 0
	i = 1
	while nums != sorted_arr:
		if i % 2 == 0:
			for j in range(2, n, 2):
				if nums[j - 1] > nums[j]:
					(nums[j - 1], nums[j]) = swap(nums[j - 1], nums[j])
			num_of_it += 1
		elif i % 2 == 1:
			for k in range(1, n, 2):
				if nums[k - 1] > nums[k]:
					(nums[k - 1], nums[k]) = swap(nums[k - 1], nums[k])
			num_of_it += 1
		i += 1
	print(num_of_it)
for i in range(n_t):
	f = input()
	nums_i = input().split()
	n = len(nums_i)
	for i in range(n):
		nums_i[i] = int(nums_i[i])
	strange_sort(nums_i)


def fsort(i, l):
	if l[i] > l[i + 1]:
		(l[i], l[i + 1]) = (l[i + 1], l[i])
	return l
t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	l2 = sorted(l)
	c = 0
	while l != l2:
		c += 1
		if c % 2 != 0:
			for i in range(0, n - 1, 2):
				l = fsort(i, l)
		else:
			for i in range(1, n - 1, 2):
				l = fsort(i, l)
	print(c)


def f(i, a):
	if i % 2 == 1:
		for j in range(len(a) - 1):
			if j % 2 == 0:
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
	else:
		for j in range(len(a) - 1):
			if j % 2 == 1:
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
	return a
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = [i for i in a]
	b.sort()
	number = 1
	count = 0
	while a != b:
		a = f(number, a)
		number += 1
		count += 1
	print(count)


from sys import *
input = stdin.readline
import random
from bisect import *
import math
from collections import *
import operator
from heapq import *
from itertools import *
inf = 10 ** 18
mod = 10 ** 9 + 7

def even():
	for i in range(1, n - 1, 2):
		if a[i] > a[i + 1]:
			(a[i], a[i + 1]) = (a[i + 1], a[i])

def odd():
	for i in range(0, n - 1, 2):
		if a[i] > a[i + 1]:
			(a[i], a[i + 1]) = (a[i + 1], a[i])
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	i = 0
	temp = sorted(a)
	while a != temp:
		i += 1
		if i % 2:
			odd()
		else:
			even()
	print(i)


def solve(n, p):
	r = 0
	while p != sorted(p):
		r += 1
		if r & 1:
			for i in range(0, n - 1, 2):
				if p[i] > p[i + 1]:
					(p[i], p[i + 1]) = (p[i + 1], p[i])
		else:
			for i in range(1, n, 2):
				if p[i] > p[i + 1]:
					(p[i], p[i + 1]) = (p[i + 1], p[i])
	return r
for _ in range(int(input())):
	print(solve(int(input()), list((int(i) for i in input().split()))))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	p = sorted(a)
	if a == p:
		print(0)
		continue
	ans = 0
	for i in range(10 ** 7):
		if i % 2 == 0:
			for j in range(0, n - 1, 2):
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		else:
			for j in range(1, n - 1, 2):
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		if p == a:
			break
	print(i + 1)


import time
from collections import deque

def inpt():
	return int(input())

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

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

def is_sorted(l):
	for i in range(len(l) - 1):
		if l[i + 1] < l[i]:
			return False
	return True

def solve():
	n = inpt()
	l = inpl()
	ans = 0
	i = 1
	while 1:
		if is_sorted(l):
			print(ans)
			return
		if i % 2 != 0:
			for j in range(0, n - 2, 2):
				if l[j] > l[j + 1]:
					(l[j], l[j + 1]) = (l[j + 1], l[j])
		else:
			for j in range(1, n - 1, 2):
				if l[j] > l[j + 1]:
					(l[j], l[j + 1]) = (l[j + 1], l[j])
		ans += 1
		i += 1

def main():
	m = 10 ** 9 + 7
	t = int(input())
	while t:
		t -= 1
		solve()
main()


y = int(input())
for i in range(y):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	b = a.copy()
	b.sort()
	j = 0
	l1 = []
	l2 = []
	for k in range(n - 1):
		if k % 2 == 0:
			l1.append(k)
		else:
			l2.append(k)
	if a == b:
		print(0)
	else:
		while a != b:
			if j % 2 == 0:
				for x in l1:
					if a[x] > a[x + 1]:
						(a[x], a[x + 1]) = (a[x + 1], a[x])
			else:
				for x in l2:
					if a[x] > a[x + 1]:
						(a[x], a[x + 1]) = (a[x + 1], a[x])
			c = c + 1
			j = j + 1
		print(c)


def f(n, a):
	a_sort = sorted(a)
	s = 0
	ind = 1
	while a != a_sort:
		if ind == 1:
			ind = 0
		else:
			ind = 1
		for i in range(ind, n - 1, 2):
			if a[i] > a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
		s += 1
	return s
n = int(input())
lst = []
for item in range(n):
	lst.append(f(int(input()), [int(item) for item in input().split()]))
print(*lst, sep='\n')


def solve():
	n = int(input())
	li = list(map(int, input().split()))
	sort = sorted(li)
	cnt = 0
	while li != sort:
		i = cnt % 2
		while i + 1 < n:
			if li[i] > li[i + 1]:
				(li[i], li[i + 1]) = (li[i + 1], li[i])
			i += 2
		cnt += 1
	print(cnt)
t = int(input())
for _ in range(t):
	solve()


from string import ascii_lowercase
from decimal import Decimal
from random import randrange, choice, randint
import time
from heapq import heappop, heappush, heapify
from copy import copy
from bisect import bisect_right, bisect_left
from sys import stdin
from functools import reduce
from math import sqrt, gcd, pi, factorial, ceil, floor, sin
from itertools import permutations
from collections import defaultdict, deque, Counter
import sys
sys.setrecursionlimit(1000000)

def sorted(a):
	n = len(a)
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			return False
	return True

def solve(n, a):
	i = 0
	while not sorted(a):
		if i % 2 == 0:
			for j in range(0, n - 1, 2):
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		else:
			for j in range(1, n - 1, 2):
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		i += 1
	return i
t = int(input())
ans = [0 for _ in range(t)]
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans[i] = solve(n, a)
for a in ans:
	print(a)


def sp(arr, x):
	for i in range(1 - x, n - x - 1, 2):
		if arr[i] > arr[i + 1]:
			(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])

def solve():
	for j in range(n):
		if arr[j] == j + 1:
			pass
		else:
			break
	else:
		return 0
	i = 1
	while True:
		if i % 2 == 0:
			sp(arr, 0)
		else:
			sp(arr, 1)
		for j in range(n):
			if arr[j] == j + 1:
				pass
			else:
				break
		else:
			return i
		i += 1
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(solve())


def f(array, i):
	if array[i] > array[i + 1]:
		(array[i], array[i + 1]) = (array[i + 1], array[i])
t = int(input())
for test_num in range(t):
	n = int(input())
	array = list(map(int, input().split()))
	notSorted = True
	iteration = 0
	while notSorted:
		notSorted = False
		for k in range(n - 1):
			if array[k] > array[k + 1]:
				notSorted = True
				iteration += 1
				break
		if iteration % 2 == 1:
			for j in range(0, n - 2, 2):
				f(array, j)
		else:
			for j in range(1, n - 1, 2):
				f(array, j)
	print(iteration)


for i in range(int(input())):
	k = int(input())
	arr = list(map(int, input().split()))
	x = 0
	arr2 = []
	while True:
		z = True
		for i in range(x % 2, k - 1, 2):
			if arr[i] > arr[i + 1]:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
				z = False
		arr2.append(z)
		try:
			if arr2[-1] == True and arr2[-2] == True:
				break
		except:
			pass
		x += 1
	print(x - 1)


import os, sys, math
from io import BytesIO, IOBase
ip = lambda : input()
it = lambda : int(input())
ma = lambda : map(int, input().split(' '))
li = lambda : list(map(int, input().split(' ')))
mod = 10 ** 9 + 7

def f(a, n, s):
	for i in range(1 - s, n - 1, 2):
		if a[i] > a[i + 1]:
			(a[i], a[i + 1]) = (a[i + 1], a[i])
	return a

def main():
	for _ in range(int(input())):
		n = it()
		a = li()
		b = sorted(a)
		i = 1
		x = 0
		while True:
			if a == b:
				break
			a = f(a, n, i)
			i = 1 - i
			x += 1
		print(x)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


for _ in range(int(input())):
	n = int(input())
	v = [int(x) for x in input().split(' ')]
	if v == sorted(v):
		print(0)
		continue
	s = 0
	while True:
		if not s % 2:
			for i in range((n - 3) // 2 + 1):
				if v[2 * i] > v[2 * i + 1]:
					(v[2 * i], v[2 * i + 1]) = (v[2 * i + 1], v[2 * i])
		elif s % 2:
			for i in range((n - 3) // 2 + 1):
				if v[2 * i + 1] > v[2 * i + 2]:
					(v[2 * i + 1], v[2 * i + 2]) = (v[2 * i + 2], v[2 * i + 1])
		s += 1
		if v == sorted(v):
			break
	print(s)


def sorte(arr):
	ans = True
	for i in range(0, len(arr)):
		if arr[i] != i + 1:
			ans = False
			break
	return ans

def odd(arr, n):
	for i in range(1, n - 1, 2):
		if arr[i - 1] > arr[i]:
			c = arr[i]
			d = arr[i - 1]
			arr[i] = d
			arr[i - 1] = c

def even(arr, n):
	for i in range(2, n, 2):
		if arr[i - 1] > arr[i]:
			c = arr[i]
			d = arr[i - 1]
			arr[i] = d
			arr[i - 1] = c
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	num = list(set(arr))
	if sorte(arr):
		print(0)
	else:
		ans = 0
		for i in range(1, n + 1):
			if sorte(arr):
				break
			elif i % 2 == 1:
				odd(arr, n)
				ans += 1
			elif i % 2 == 0:
				even(arr, n)
				ans += 1
		print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	i = 1
	s = [o for o in a]
	s.sort()
	while s != a:
		if i % 2 == 0:
			for j in range(1, n - 1, 2):
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		else:
			for j in range(0, n - 2, 2):
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		i += 1
	print(i - 1)


import sys
from math import sqrt, ceil, floor, gcd
from collections import Counter
input = lambda : sys.stdin.readline()

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

def str_arr():
	return list(map(str, input().split()))

def get_str():
	return map(str, input().split())

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

def get_flo():
	return map(float, input().split())

def lcm(a, b):
	return a * b // gcd(a, b)
mod = 1000000007

def solve(n, a):
	sortedA = sorted(a)
	c = 0
	while sortedA != a:
		for i in range(c % 2, n - 1, 2):
			if a[i] > a[i + 1]:
				(a[i + 1], a[i]) = (a[i], a[i + 1])
		c += 1
	print(c)
for _ in range(int(input())):
	n = int(input())
	a = int_arr()
	solve(n, a)


for a in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	ll = sorted(l)
	c = 0
	while l != ll:
		for i in range(c % 2, n - 1, 2):
			if l[i] > l[i + 1]:
				(l[i], l[i + 1]) = (l[i + 1], l[i])
		c += 1
	print(c)


def main():

	def f(a, i):
		i -= 1
		if (save := a[i]) > a[i + 1]:
			a[i] = a[i + 1]
			a[i + 1] = save
		return a
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		sa = list(sorted(a))
		c = 1
		while a != sa:
			if c % 2:
				for i in range(1, n - 1, 2):
					a = f(a, i)
			else:
				for i in range(2, n, 2):
					a = f(a, i)
			if c > 1000:
				break
			c += 1
		print(c - 1)
main()


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

def getmapint():
	return map(int, stdin.readline().split())

def getliststr():
	return list(stdin.readline().split())

def getint():
	return int(stdin.readline().strip())

def getstr():
	return stdin.readline().strip()

def pr(s):
	stdout.write(str(s) + '\n')

def prlist(l):
	stdout.write(' '.join(list(map(str, l))) + '\n')
from sys import stdin, stdout
for _ in range(getint()):
	n = getint()
	a = getlistint()
	l = sorted(a)
	j = 0
	while l != a:
		j += 1
		if j % 2 == 1:
			for i in range(0, n - 2, 2):
				if a[i] > a[i + 1]:
					(a[i], a[i + 1]) = (a[i + 1], a[i])
		else:
			for i in range(1, n - 1, 2):
				if a[i] > a[i + 1]:
					(a[i], a[i + 1]) = (a[i + 1], a[i])
	pr(j)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	steps = 0
	turn = 0
	while a != list(range(1, n + 1)):
		for i in range(turn, n - 1, 2):
			if a[i] > a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
		turn ^= 1
		steps += 1
	print(steps)


import sys
import math
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	data = list(map(int, input().split()))
	ans = 0
	check = True
	for i in range(n):
		if data[i] != i + 1:
			check = False
			break
	while not check:
		check = True
		ans += 1
		k = (ans - 1) % 2
		for i in range(n):
			if i % 2 == k and i + 1 < n:
				if data[i] > data[i + 1]:
					(data[i], data[i + 1]) = (data[i + 1], data[i])
			if data[i] != i + 1:
				check = False
	print(ans)


def issorted(n, a):
	for i in range(1, n):
		if a[i] < a[i - 1]:
			return False
	return True

def solve(n, a):
	i = 0
	while not issorted(n, a):
		if i % 2 == 0:
			for j in range(0, n, 2):
				if j + 1 < n and a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		else:
			for j in range(1, n, 2):
				if j + 1 < n and a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		i += 1
	return i
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(solve(n, a))


T = int(input().strip())
for t in range(T):
	N = int(input().strip())
	A = list(map(int, input().split()))
	AS = sorted(A)
	iterations = 0
	if A == AS:
		print(0)
		continue

	def func(i):
		if i % 2 == 1:
			for idx in range(1, N - 1, 2):
				if A[idx] > A[idx + 1]:
					(A[idx], A[idx + 1]) = (A[idx + 1], A[idx])
		else:
			for idx in range(0, N - 2, 2):
				if A[idx] > A[idx + 1]:
					(A[idx], A[idx + 1]) = (A[idx + 1], A[idx])
	while True:
		for i in range(N + 1):
			func(i)
			iterations += 1
			if A == AS:
				print(iterations)
				break
		break


import sys
from math import *
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	ans = 0
	while b != a:
		ans += 1
		if ans % 2 == 1:
			for i in range(0, n - 1, 2):
				if a[i] > a[i + 1]:
					(a[i], a[i + 1]) = (a[i + 1], a[i])
		else:
			for i in range(1, n, 2):
				if a[i] > a[i + 1]:
					(a[i], a[i + 1]) = (a[i + 1], a[i])
	print(ans)


def temp(i, array):
	if array[i] > array[i + 1]:
		tem = array[i]
		array[i] = array[i + 1]
		array[i + 1] = tem

def fn(array):
	cnt = 0
	n = len(array)
	arr = [i for i in range(1, n + 1)]
	if arr == array:
		return 0
	i = 0
	while True:
		if i % 2 == 0:
			for j in range(0, n - 2, 2):
				temp(j, array)
			cnt += 1
		else:
			for j in range(1, n - 1, 2):
				temp(j, array)
			cnt += 1
		if arr == array:
			break
		i += 1
	return cnt
t = int(input())
for i in range(t):
	n = int(input())
	array = list(map(int, input().strip().split()))
	print(fn(array))


import sys
from os import path
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
t = int(input())
for i in range(t):
	n = int(input())
	line = input()
	arr = line.split(' ')
	for i in range(n):
		arr[i] = int(arr[i])
	swaps = 0
	sortedarr = arr.copy()
	sortedarr.sort()
	if arr == sortedarr:
		print(0)
	else:
		xx = True
		while swaps >= 0:
			swaps += 1
			if xx:
				xx = False
				for i in range(0, n - 2, 2):
					if arr[i] > arr[i + 1]:
						(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			else:
				xx = True
				for i in range(1, n - 1, 2):
					if arr[i] > arr[i + 1]:
						(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			if arr == sortedarr:
				break
		print(swaps)


def func(ind, num_of_iterations):
	num_of_iterations += 1
	ind2 = ind % 2
	while ind2 < n - 1:
		if a[ind2] > a[ind2 + 1]:
			(a[ind2 + 1], a[ind2]) = (a[ind2], a[ind2 + 1])
		ind2 += 2
	return num_of_iterations
for _ in range(int(input())):
	n = int(input())
	a = [int(num) for num in input().split()]
	b = sorted(a)
	num_of_iterations = 0
	for ind in range(n * (n - 1) // 2):
		if a == b:
			break
		num_of_iterations = func(ind % n, num_of_iterations)
	print(num_of_iterations)


def sort(arr, n):
	ans = True
	for i in range(0, n):
		if arr[i] != i + 1:
			ans = False
			break
	return ans

def itrodd(arr, n):
	for i in range(1, n - 1, 2):
		if arr[i - 1] > arr[i]:
			b = arr[i]
			h = arr[i - 1]
			arr[i] = h
			arr[i - 1] = b

def itreven(arr, n):
	for i in range(2, n, 2):
		if arr[i - 1] > arr[i]:
			b = arr[i]
			h = arr[i - 1]
			arr[i] = h
			arr[i - 1] = b
test = int(input())
while test > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	total = 0
	for i in range(1, n + 1):
		if sort(arr, n):
			break
		elif i % 2 == 0:
			itreven(arr, n)
			total += 1
		else:
			itrodd(arr, n)
			total += 1
	print(total)
	test -= 1


import math
x = int(input())
for i in range(x):
	n = int(input())
	x = input().split()
	for j in range(n):
		x[j] = int(x[j])
	b = []
	for k in x:
		b.append(k)
	x.sort()
	count = 0
	while x != b:
		if x != b:
			for l in range(0, n - 1, 2):
				if b[l] > b[l + 1]:
					(b[l], b[l + 1]) = (b[l + 1], b[l])
			count += 1
		if x != b:
			for p in range(1, n - 1, 2):
				if b[p] > b[p + 1]:
					(b[p], b[p + 1]) = (b[p + 1], b[p])
			count += 1
	print(count)


n = int(input())

def func1(index1, length1, array1):
	while index1 < length1 - 1:
		if array1[index1] > array1[index1 + 1]:
			(array1[index1], array1[index1 + 1]) = (array1[index1 + 1], array1[index1])
		index1 += 2
for _ in range(n):
	length = int(input())
	array = list(map(int, input().split()))
	state = True
	index = 0
	count = 0
	while array != sorted(array):
		func1(index % 2, length, array)
		index += 1
	print(index)


def sort_check(n, ar):
	flag = 0
	for i in range(n):
		if flag:
			break
		if i + 1 != ar[i]:
			flag = 1
	return flag

def solve(n, l):
	count = 0
	while sort_check(n, l):
		if count % 2 == 0:
			for i in range(0, n - 1, 2):
				if l[i] > l[i + 1]:
					temp = l[i]
					l[i] = l[i + 1]
					l[i + 1] = temp
			count += 1
		else:
			for i in range(1, n - 1, 2):
				if l[i] > l[i + 1]:
					temp = l[i]
					l[i] = l[i + 1]
					l[i + 1] = temp
			count += 1
	return count
t = int(input())
for i in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	print(solve(n, ar))


def check(arr, start):
	res = True
	while start + 1 < len(arr):
		if arr[start] > arr[start + 1]:
			res = False
			t = arr[start]
			arr[start] = arr[start + 1]
			arr[start + 1] = t
		start += 2
	return res

def solve(arr):
	odd = False
	even = False
	for i in range(1, 2 * len(arr)):
		if i % 2 == 0:
			even = check(arr, 1)
		else:
			odd = check(arr, 0)
		if even and odd:
			return i - 2
T = int(input())
for t in range(1, T + 1):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(solve(arr))


def f(a, i):
	if a[i + 1] <= a[i]:
		(a[i], a[i + 1]) = (a[i + 1], a[i])

def check(a):
	for i in range(len(a) - 1):
		if a[i + 1] < a[i]:
			return False
	return True

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	while not check(a):
		if c % 2 == 0:
			for i in range(0, len(a) - 1, 2):
				f(a, i)
		else:
			for i in range(1, len(a), 2):
				f(a, i)
		c += 1
	return c
for i in range(int(input())):
	print(solve())


for __ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	(obj, iterations) = (list(range(1, N + 1)), 0)
	while A != obj:
		for i in range(iterations % 2, N - 1, 2):
			if A[i + 1] < A[i]:
				A[i:i + 2] = A[i:i + 2][::-1]
		iterations += 1
	print(iterations)


def eve(l):
	for i in range(0, n - 1, 2):
		if l[i] > l[i + 1]:
			(l[i], l[i + 1]) = (l[i + 1], l[i])
	return l

def odd(l):
	for i in range(1, n - 1, 2):
		if l[i] > l[i + 1]:
			(l[i], l[i + 1]) = (l[i + 1], l[i])
	return l
x = int(input())
while x:
	x -= 1
	n = int(input())
	l = list(map(int, input().split()))
	m = l
	if m == sorted(l):
		print(0)
	else:
		c = 0
		for i in range(n):
			if i & 1:
				m = odd(m)
				if m == sorted(l):
					print(c + 1)
					break
				else:
					c += 1
			else:
				m = eve(m)
				if m == sorted(l):
					print(c + 1)
					break
				else:
					c += 1


for i in range(int(input())):
	t = int(input())
	k = list(map(int, input().split()))
	m = sorted(k)
	c = 0
	while k != m:
		for j in range(c % 2, len(k) - 1, 2):
			if k[j] > k[j + 1]:
				(k[j], k[j + 1]) = (k[j + 1], k[j])
		c += 1
	print(c)


for i in range(int(input())):
	c = int(input())
	x = list(map(int, input().split()))
	y = sorted(x)
	for j in range(c ** 2):
		if x == y:
			print(0)
			break
		n = j % 2
		for i in range(c // 2):
			i = 2 * i
			if x[i + n] > x[i + 1 + n]:
				(x[i + n], x[i + 1 + n]) = (x[i + 1 + n], x[n + i])
		if x == y:
			print(j + 1)
			break


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ls = sorted(l)
	c = 0
	while l != ls:
		j = c % 2
		c += 1
		for i in range(j, n - 1, 2):
			if l[i] > l[i + 1]:
				(l[i], l[i + 1]) = (l[i + 1], l[i])
	print(c)


import sys
input = sys.stdin.readline

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		ar = list(map(int, input().split()))
		g = list(range(1, n + 1))
		ans = 0
		for x in range(1, n * n + 1):
			if ar == g:
				break
			if x % 2:
				for j in range(0, n + 1, 2):
					if j + 1 <= n - 1:
						if ar[j] > ar[j + 1]:
							(ar[j], ar[j + 1]) = (ar[j + 1], ar[j])
				ans += 1
			else:
				for j in range(1, n + 1, 2):
					if j + 1 <= n - 1:
						if ar[j] > ar[j + 1]:
							(ar[j], ar[j + 1]) = (ar[j + 1], ar[j])
				ans += 1
		print(ans)
main()


def f(i):
	if i & 1:
		for j in range(0, n, 2):
			if j + 1 < n and a[j] > a[j + 1]:
				temp = a[j]
				a[j] = a[j + 1]
				a[j + 1] = temp
	else:
		for j in range(1, n, 2):
			if j + 1 < n and a[j] > a[j + 1]:
				temp = a[j]
				a[j] = a[j + 1]
				a[j + 1] = temp
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	best = sorted(a)
	ans = 0
	while a != best:
		ans += 1
		f(ans)
	print(ans)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	i = 0
	tem = sorted(a)
	while 1:
		if a == tem:
			break
		if i % 2 == 0:
			for x in range(0, n - 1, 2):
				if a[x] > a[x + 1]:
					(a[x], a[x + 1]) = (a[x + 1], a[x])
		else:
			for x in range(1, n - 1, 2):
				if a[x] > a[x + 1]:
					(a[x], a[x + 1]) = (a[x + 1], a[x])
		i += 1
	print(i)


from collections import Counter
import math
from bisect import bisect
import sys
MOD = 1000000007
MAX = sys.maxsize
MIN = -sys.maxsize

class get:

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

	def str():
		return input().split()

	def float():
		return list(map(float, input().split()))

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

def sqrt(x):
	return int(math.sqrt(x)) + 1

def gcd(*args):
	result = args[0]
	for item in args:
		result = math.gcd(result, item)
	return result

def LCM(a, b):
	return a * b // math.gcd(a, b)

def solve():
	n = int(input())
	arr = get.int()
	i = 1
	while True:
		kk = arr + []
		kk.sort()
		if kk == arr:
			print(i - 1)
			break
		if i % 2 == 0:
			for j in range(1, n, 2):
				if j + 1 < n and arr[j] > arr[j + 1]:
					(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
		elif i % 2 != 0:
			for j in range(0, n, 2):
				if j + 1 < n and arr[j] > arr[j + 1]:
					(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
		i += 1
for _ in range(int(input())):
	solve()


import copy
import math
from sys import stdin

def A():
	t = int(stdin.readline())
	while t:
		t -= 1
		n = int(stdin.readline())
		a = [int(x) for x in stdin.readline().split()]
		b = copy.deepcopy(a)
		b.sort()
		if a == b:
			print(0)
		else:
			i = 1
			while a != b:
				if i % 2 == 0:
					for j in range(0, n):
						if (j + 1) % 2 == 0:
							if j < n - 1:
								if a[j] > a[j + 1]:
									(a[j], a[j + 1]) = (a[j + 1], a[j])
				else:
					for j in range(0, n):
						if (j + 1) % 2 == 1:
							if j < n - 1:
								if a[j] > a[j + 1]:
									(a[j], a[j + 1]) = (a[j + 1], a[j])
				i += 1
			print(i - 1)

def B():
	t = int(stdin.readline())
	while t:
		t -= 1
		(a, b, c) = [int(x) for x in stdin.readline().split()]

def C():
	t = int(stdin.readline())
	while t:
		t -= 1
		a = [int(x) for x in stdin.readline().split()]

def D():
	t = int(stdin.readline())

def F1():
	t = int(stdin.readline())
	while t:
		t -= 1
A()


import bisect
import heapq
import math
import collections
import sys
import copy
from functools import reduce
import decimal
from io import BytesIO, IOBase
import os
import itertools
import functools
from types import GeneratorType
sys.setrecursionlimit(10 ** 9)
decimal.getcontext().rounding = decimal.ROUND_HALF_UP
graphDict = collections.defaultdict
queue = collections.deque

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		to = f(*args, **kwargs)
		if stack:
			return to
		else:
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						return to
					to = stack[-1].send(to)
	return wrappedfunc

class Graphs:

	def __init__(self):
		self.graph = graphDict(set)

	def add_edge(self, u, v):
		self.graph[u].add(v)
		self.graph[v].add(u)

	def dfs_utility(self, nodes, visited_nodes, psf):
		global ans
		if len(visited_nodes.keys()) == n:
			ans = psf
			return
		visited_nodes[nodes] = None
		for neighbour in self.graph[nodes]:
			if neighbour not in visited_nodes:
				self.dfs_utility(neighbour, visited_nodes, psf + [neighbour])
		visited_nodes.pop(nodes)
		return

	def dfs(self, node):
		global ans
		Visited = collections.OrderedDict()
		self.dfs_utility(node, Visited, [node])

	def bfs(self, node):
		visited = set()
		if node not in visited:
			queue.append(node)
			visited.add(node)
		while queue:
			parent = queue.popleft()
			print(parent)
			for item in self.graph[parent]:
				if item not in visited:
					queue.append(item)
					visited.add(item)

class Tree:

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

def inorder(node, lis):
	if node:
		inorder(node.left, lis)
		lis.append(node.data)
		inorder(node.right, lis)
	return lis

def leaf_node_sum(root):
	if root is None:
		return 0
	if root.left is None and root.right is None:
		return root.data
	return leaf_node_sum(root.left) + leaf_node_sum(root.right)

def hight(root):
	if root is None:
		return -1
	if root.left is None and root.right is None:
		return 0
	return max(hight(root.left), hight(root.right)) + 1

def rounding(n):
	return int(decimal.Decimal(f'{n}').to_integral_value())

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0), []))

def p_sum(array):
	return list(itertools.accumulate(array))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, **kwargs):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

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

def map_inp(v_type):
	return map(v_type, inp().split())

def list_inp(v_type):
	return list(map_inp(v_type))
for _ in range(int(inp())):
	n = int(inp())
	arr = list_inp(int)
	temp = list(sorted(arr))
	count = 0
	for i in range(1, n + 1):
		flag = 0
		for (q, w) in zip(temp, arr):
			if q != w:
				flag = 1
				break
		if flag == 0:
			break
		count += 1
		if i & 1:
			for j in range(1, n, 2):
				if arr[j - 1] > arr[j]:
					(arr[j - 1], arr[j]) = (arr[j], arr[j - 1])
		else:
			for j in range(2, n + 1, 2):
				if arr[j - 1] > arr[j]:
					(arr[j - 1], arr[j]) = (arr[j], arr[j - 1])
	print(count)


def sol():
	n = int(input())
	arr = list(map(int, input().split()))
	p = sorted(arr)
	for i in range(len(arr)):
		if arr == p:
			print(i)
			return
		for j in range(i % 2, len(arr) - 1, 2):
			if arr[j] > arr[j + 1]:
				m = arr[j]
				arr[j] = arr[j + 1]
				arr[j + 1] = m
	print(len(arr))
for _ in range(int(input())):
	sol()


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(2 * 10 ** 5 + 10)
write = lambda x: sys.stdout.write(x + '\n')
debug = lambda x: sys.stderr.write(x + '\n')
writef = lambda x: print('{:.12f}'.format(x))
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	sa = sorted(a)
	ans = 0
	p = 1
	j = 0
	while sa != a:
		ans += 1
		j += 1
		if j % 2 == 1:
			for i in range(0, n - 1, 2):
				if a[i] > a[i + 1]:
					(a[i], a[i + 1]) = (a[i + 1], a[i])
					f = 1
		else:
			for i in range(1, n - 1, 2):
				if a[i] > a[i + 1]:
					(a[i], a[i + 1]) = (a[i + 1], a[i])
					f = 1
	print(ans)


for i in range(int(input())):
	(a, b) = ([], [])
	c = 0
	l = int(input())
	el = input().split()
	for elems in el:
		a.append(int(elems))
		b.append(int(elems))
	it = 1
	b.sort()
	while a != b:
		if it % 2 == 0:
			for k in range(1, len(a), 2):
				j = k + 1
				if a[k] > a[j]:
					(a[k], a[j]) = (a[j], a[k])
			it += 1
		else:
			for k in range(0, len(a) - 1, 2):
				j = k + 1
				if a[k] > a[j]:
					(a[k], a[j]) = (a[j], a[k])
			it += 1
	print(it - 1)


def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		b = list(sorted(a))
		if b == a:
			print(0)
			continue
		for i in range(n):
			if not i % 2:
				for j in range(0, n, 2):
					a[j:j + 2] = sorted(a[j:j + 2])
			else:
				for j in range(1, n, 2):
					a[j:j + 2] = sorted(a[j:j + 2])
			if a == b:
				print(i + 1)
				break
main()


TC = int(input())
for tc in range(TC):
	N = int(input())
	A = list(map(int, input().split()))
	ok = False
	result = 0
	while not ok:
		ok = True
		if A[0] > A[1]:
			(A[0], A[1]) = (A[1], A[0])
			ok = False
		for i in range(2, N - 1, 2):
			if A[i] > A[i + 1]:
				(A[i], A[i + 1]) = (A[i + 1], A[i])
				ok = False
			if A[i - 1] > A[i]:
				ok = False
		if A[-2] > A[-1]:
			ok = False
		if ok:
			break
		else:
			result += 1
		ok = True
		if A[1] > A[2]:
			(A[1], A[2]) = (A[2], A[1])
			ok = False
		if A[0] > A[1]:
			ok = False
		for i in range(3, N - 1, 2):
			if A[i] > A[i + 1]:
				(A[i], A[i + 1]) = (A[i + 1], A[i])
				ok = False
			if A[i - 1] > A[i]:
				ok = False
		if ok:
			break
		else:
			result += 1
	print(result)


def func():
	t = int(input().strip())
	cases = []
	for _ in range(t):
		n = int(input().strip())
		a = list(map(int, input().strip().split()))
		cases.append([a, n])
	for case in cases:
		print(simple_sort(case[0], case[1]))

def simple_sort(nums, n):
	ans = 0
	nums_sorted = sorted(nums)
	while nums != nums_sorted:
		for i in range(ans % 2, n - 1, 2):
			if nums[i] > nums[i + 1]:
				(nums[i], nums[i + 1]) = (nums[i + 1], nums[i])
		ans += 1
	return ans
func()


def solve(n, a):
	s = sorted(a)
	count = 0
	j = 0
	while a != s:
		if j % 2 == 0:
			for i in range(0, n - 1, 2):
				if a[i] > a[i + 1]:
					(a[i], a[i + 1]) = (a[i + 1], a[i])
		else:
			for i in range(1, n - 1, 2):
				if a[i] > a[i + 1]:
					(a[i], a[i + 1]) = (a[i + 1], a[i])
		count += 1
		j += 1
	return count
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


import sys, os, io
import math
from collections import defaultdict
from io import BytesIO, IOBase
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	input = lambda : sys.stdin.readline().rstrip('\r\n')

def solve():
	n = ii()
	a = li()
	cnt = 0
	a1 = a[:]
	a1.sort()
	while a1 != a:
		if cnt % 2 == 0:
			for i in range(0, n, 2):
				if i + 1 == n:
					break
				if a[i + 1] < a[i]:
					(a[i + 1], a[i]) = (a[i], a[i + 1])
		else:
			for i in range(1, n, 2):
				if i + 1 == n:
					break
				if a[i + 1] < a[i]:
					(a[i + 1], a[i]) = (a[i], a[i + 1])
		cnt += 1
	print(cnt)
t = 1
t = ii()
for _ in range(t):
	solve()


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

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

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

def get_int():
	return int(sys.stdin.readline().strip())

def get_list_strings():
	return list(map(str, sys.stdin.readline().strip().split()))

def solve(n, arr):
	count = 0
	final = arr[:]
	final.sort()
	while final != arr:
		for i in range(0, n - 2, 2):
			if arr[i] > arr[i + 1]:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		count += 1
		if final == arr:
			break
		for i in range(1, n - 1, 2):
			if arr[i] > arr[i + 1]:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		count += 1
	sys.stdout.write(str(count) + '\n')
	return
T = get_int()
while T:
	n = get_int()
	arr = get_list()
	solve(n, arr)
	T -= 1


def f(a, i):
	if a[i - 1] > a[i]:
		(a[i - 1], a[i]) = (a[i], a[i - 1])
	return a

def check_sort(a, a_len):
	check_list = [True for (i, j) in zip(a[:-1], a[1:]) if i < j]
	if len(check_list) == a_len - 1:
		return True
	else:
		return False

def iteration(a, i, a_len):
	if i % 2 == 0:
		for j in range(2, a_len, 2):
			a = f(a, j)
	else:
		for j in range(1, a_len - 1, 2):
			a = f(a, j)
	return a

def sort_iter_count(a, a_len):
	iter_n = 1
	while not check_sort(a, a_len):
		a = iteration(a, iter_n, a_len)
		iter_n += 1
	print(iter_n - 1)
permutations_n = int(input())
for _ in range(permutations_n):
	permutation_len = int(input())
	permutation = [int(x) for x in input().split()]
	sort_iter_count(permutation, permutation_len)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	b = []
	for i in range(n):
		b.append(l[i])
	b.sort()

	def solve(n, l):
		c = 0
		for i in range(n):
			x = 0
			if i % 2 == 0:
				for i in range(0, n - 1, 2):
					if l[i] > l[i + 1]:
						x = 1
						(l[i], l[i + 1]) = (l[i + 1], l[i])
				if x == 1:
					c += 1
			else:
				for i in range(1, n - 1, 2):
					if l[i] > l[i + 1]:
						x = 1
						(l[i], l[i + 1]) = (l[i + 1], l[i])
				if x == 1:
					c += 1
			if x == 0 and l != b:
				c += 1
		return c
	print(solve(n, l))


def f(arr, i):
	if arr[i] > arr[i + 1]:
		(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])

def iterate(arr, i):
	n = len(arr)
	if i % 2:
		for j in range(0, n - 1, 2):
			f(arr, j)
	else:
		for j in range(1, n - 1, 2):
			f(arr, j)
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	srt = sorted(arr)
	i = 1
	res = 0
	while arr != srt:
		iterate(arr, i)
		i ^= 1
		res += 1
	print(res)


def sp(arr, x):
	for i in range(1 - x, n - x - 1, 2):
		if arr[i] > arr[i + 1]:
			(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])

def solve():
	if arr == sorted(arr):
		return 0
	i = 1
	while True:
		sp(arr, i % 2)
		if arr == sorted(arr):
			return i
		i += 1
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(solve())


def subsets_gen(num):

	def generator_h(no, s):
		if len(s) == no:
			yield s
		else:
			yield from generator_h(no, s + '0')
			yield from generator_h(no, s + '1')
	yield from generator_h(num, '')

def perms_gen(pole):
	used = [False for i in range(len(pole))]

	def generator_h(l, m):
		if len(m) == len(l):
			yield m
		else:
			for i in range(len(l)):
				if used[i]:
					continue
				else:
					m.append(l[i])
					used[i] = True
					yield from generator_h(l, m)
					m.pop()
					used[i] = False
	yield from generator_h(pole, [])

def fact(n):
	factors = []
	if n % 2 == 0:
		while n % 2 == 0:
			factors.append(2)
			n //= 2
	poc = 3
	while poc * poc <= n:
		while n % poc == 0:
			factors.append(poc)
			n //= poc
		poc += 2
	if n > 1:
		factors.append(n)
	return factors

def gcd(a, b):
	if a % b == 0:
		return b
	else:
		return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def NcK(n, k):
	if k == 0 or k == n:
		return 1
	return NcK(n - 1, k - 1) + NcK(n - 1, k)
testcases = 1
testcases = int(input())
for _ in range(testcases):
	n = int(input())
	zoz = [int(x) for x in input().split()]
	zoz1 = sorted(zoz)
	cnt = 0
	while True:
		flag = False
		if cnt % 2 == 1:
			for i in range(1, n - 1, 2):
				if zoz[i] > zoz[i + 1]:
					(zoz[i], zoz[i + 1]) = (zoz[i + 1], zoz[i])
					flag = True
		else:
			for i in range(0, n - 2, 2):
				if zoz[i] > zoz[i + 1]:
					(zoz[i], zoz[i + 1]) = (zoz[i + 1], zoz[i])
					flag = True
		if not flag and zoz == zoz1:
			print(cnt)
			break
		cnt += 1


import sys
input = sys.stdin.readline

def ri():
	return [int(i) for i in input().split()]

def main():
	j = ri()[0]
	for _ in range(j):
		n = ri()[0]
		a = ri()
		b = sorted(a)
		if a == b:
			print(0)
			continue
		for i in range(1, 10000):
			odd = i % 2
			_from = 0 if odd == 1 else 1
			_to = n - 2 if odd == 1 else n - 1
			for j in range(_from, _to, 2):
				if a[j + 1] < a[j]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
			if a == b:
				print(i)
				break
main()


import sys
input = sys.stdin.readline

def solution(n, arr):
	ans = 0
	while True:
		is_sorted = True
		for i in range(n):
			if arr[i] != i + 1:
				is_sorted = False
				break
		if is_sorted:
			return ans
		if (ans + 1) % 2 != 0:
			for i in range(0, n, 2):
				if i + 1 < n and arr[i] > arr[i + 1]:
					tmp = arr[i]
					arr[i] = arr[i + 1]
					arr[i + 1] = tmp
		else:
			for i in range(1, n, 2):
				if i + 1 < n and arr[i] > arr[i + 1]:
					tmp = arr[i]
					arr[i] = arr[i + 1]
					arr[i + 1] = tmp
		ans += 1
t = int(input())
while t:
	t -= 1
	n = int(input())
	arr = [int(x) for x in input().strip().split(' ')]
	print(solution(n, arr))


t = int(input())
ans = []
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	s = True
	ret = 0
	for j in range(n):
		s = False
		nd = j & 1
		for i in range(nd, n - 1, 2):
			if a[i] > a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
				s = True
		if s:
			if j == 1 and ret == 0:
				ret = 2
			else:
				ret += 1
		elif nd:
			break
	ans.append(str(ret))
print('\n'.join(ans))


from sys import stdin
from collections import deque, Counter, defaultdict, OrderedDict
import sys
import math, os
import operator
import random
from fractions import Fraction
import functools
import bisect
import itertools
from heapq import *
import time
import copy
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	newarr = sorted(arr)
	i = 1
	while arr != newarr:
		if i % 2 == 0:
			for j in range(1, n, 2):
				if j + 1 < n and arr[j] > arr[j + 1]:
					(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
		else:
			for j in range(0, n, 2):
				if j + 1 < n and arr[j] > arr[j + 1]:
					(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
		i += 1
	print(i - 1)


from sys import stdin
inp = stdin.readline
t = int(inp())
for _ in range(t):
	n = int(inp())
	arr = [int(x) for x in inp().split()]
	ans = arr[:]
	ans.sort()
	i = 0
	while True:
		if arr == ans:
			break
		if not i % 2:
			for j in range(n // 2):
				if arr[2 * j] > arr[2 * j + 1]:
					(arr[2 * j], arr[2 * j + 1]) = (arr[2 * j + 1], arr[2 * j])
		else:
			for j in range(n // 2):
				if arr[2 * j + 1] > arr[2 * j + 2]:
					(arr[2 * j + 2], arr[2 * j + 1]) = (arr[2 * j + 1], arr[2 * j + 2])
		i += 1
	print(i)


def f(x):
	i = 0
	while i < len(x) - 1:
		if x[i] > x[i + 1]:
			X = x[i + 1]
			x[i + 1] = x[i]
			x[i] = X
		i = i + 2
	return x

def g(x):
	i = 1
	while i < len(x) - 1:
		if x[i] > x[i + 1]:
			X = x[i + 1]
			x[i + 1] = x[i]
			x[i] = X
		i = i + 2
	return x
z = int(input())
while z > 0:
	l = int(input())
	L = [int(i) for i in input().split(' ')]
	X = L[:]
	X.sort()
	n = 0
	N = 0
	while X != L:
		if N == 0:
			L = f(L)
			N = 1
			n = n + 1
		else:
			L = g(L)
			N = 0
			n = n + 1
	print('{}'.format(n))
	z = z - 1


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

def f(arr, i):
	if arr[i] > arr[i + 1]:
		(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])

def step(arr, i):
	if i % 2 == 1:
		for j in range(0, n - 2, 2):
			f(arr, j)
	else:
		for j in range(1, n - 1, 2):
			f(arr, j)

def get_num_iter(perm):
	iterations = 0
	while not ordered(perm):
		step(perm, iterations + 1)
		iterations += 1
	return iterations
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	arr = [int(el) for el in s.split(' ')]
	print(get_num_iter(arr))


n = int(input(''))
x = []
y = []
iterations = []
for i in range(n):
	nn = int(input(''))
	nnn = input('')
	x.append(list(map(int, nnn.split(' '))))
	y = x[i].copy()
	y.sort()
	itr = -1
	while x[i] != y:
		itr += 1
		for j in range(len(x[i])):
			if itr % 2 != 0:
				if j % 2 != 0:
					if x[i][j] > x[i][j + 1]:
						(x[i][j], x[i][j + 1]) = (x[i][j + 1], x[i][j])
			elif j != len(x[i]) - 1:
				if j % 2 == 0:
					if x[i][j] > x[i][j + 1]:
						(x[i][j], x[i][j + 1]) = (x[i][j + 1], x[i][j])
	iterations.append(itr + 1)
for iteration in iterations:
	print(iteration)


def int_input():
	a = int(input())
	return a

def int_list_input():
	a = list(map(int, input().split()))
	return a

def solve():
	n = int_input()
	arr = int_list_input()
	ans = 0
	iteration = 1
	while True:
		flag = True
		for i in range(n):
			if arr[i] != i + 1:
				flag = False
				break
		if flag:
			break
		ans += 1
		if iteration % 2 != 0:
			i = 0
			while i < n and i + 1 < n:
				if arr[i] < arr[i + 1]:
					i += 2
					continue
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
				i += 2
		else:
			i = 1
			while i < n and i + 1 < n:
				if arr[i] < arr[i + 1]:
					i += 2
					continue
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
				i += 2
		iteration += 1
	print(ans)
for _ in range(int(input())):
	solve()


import os
import sys
from io import BytesIO, IOBase
import math
from decimal import Decimal
from decimal import *
from collections import defaultdict, deque
import heapq
import bisect
from decimal import Decimal
getcontext().prec = 25
abcd = 'abcdefghijklmnopqrstuvwxyz'
ABCD = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
months = {1: 31, 2: 28, 3: 31, 4: 30, 5: 31, 6: 30, 7: 31, 8: 31, 9: 30, 10: 31, 11: 30, 12: 31}
MOD = 1000000007
BUFSIZE = 8192
from bisect import bisect_left, bisect_right

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	ans = 0
	j = 0
	f = sorted(l)
	while l != f:
		if j % 2 == 0:
			for i in range(0, n - 1, 2):
				if l[i] > l[i + 1]:
					(l[i], l[i + 1]) = (l[i + 1], l[i])
		else:
			for i in range(1, n, 2):
				if l[i] > l[i + 1]:
					(l[i], l[i + 1]) = (l[i + 1], l[i])
		ans += 1
		j += 1
	print(ans)


a = int(input())
for i in range(int(a)):
	b = input()
	lst_ = input().split(' ')
	lst = [int(elem) for elem in lst_]
	srt = sorted(lst)
	num = 1
	if srt == lst:
		print('0')
		continue
	while srt != lst:
		if int(num % 2) == 1:
			for k in range(0, len(lst) - 1, 2):
				if lst[k] > lst[k + 1]:
					c = lst[k + 1]
					lst[k + 1] = lst[k]
					lst[k] = c
			num += 1
			continue
		if int(num % 2) == 0:
			for k in range(1, len(lst), 2):
				if lst[k] > lst[k + 1]:
					c = lst[k + 1]
					lst[k + 1] = lst[k]
					lst[k] = c
			num += 1
			continue
	print(num - 1)


import os
import sys

def main():
	fastReadInt = sys.stdin.buffer.readline

	def fastReadStr():
		return sys.stdin.buffer.readline().decode('utf-8').strip()

	def fastWrite(ans):
		return sys.stdout.buffer.write(str(str(ans) + '\n').encode('utf-8'))

	def fastWriteList(ans):
		return sys.stdout.buffer.write(str(' '.join(map(str, ans)) + '\n').encode('utf-8'))
	DEBUG = 'DEBUG' in os.environ

	def debug(*args):
		if DEBUG:
			print('>', *args)

	def sortStep(a, b):
		if a > b:
			return [b, a]
		return [a, b]

	def solution(value):
		lenn = len(value)
		valueToSort = value.copy()
		sortedValue = value.copy()
		sortedValue.sort()
		res = 0
		while valueToSort != sortedValue:
			idx = 2 if res % 2 else 1
			while idx < lenn:
				aft = sortStep(valueToSort[idx - 1], valueToSort[idx])
				valueToSort[idx - 1] = aft[0]
				valueToSort[idx] = aft[1]
				idx += 2
			res += 1
		fastWrite(res)
	for t in range(int(fastReadInt())):
		length = fastReadInt()
		solution(list(map(int, fastReadInt().split())))
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a.copy())
	ans = 0
	while a != b:
		for i in range(ans % 2, n - 1, 2):
			if a[i] > a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
		ans += 1
	print(ans)


for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	sr = sorted(arr)
	c = 0
	while arr != sr:
		for j in range(c % 2, len(arr) - 1, 2):
			if arr[j] > arr[j + 1]:
				(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
		c += 1
	print(c)


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	cnt = 0
	b = a[:]
	b.sort()
	for i in range(n):
		if a == b:
			break
		cnt += 1
		for j in range(i % 2, n, 2):
			if j + 1 == n:
				break
			if a[j] > a[j + 1]:
				(a[j], a[j + 1]) = (a[j + 1], a[j])
	print(cnt)


def main():
	N = int(input())
	A = list(map(int, input().split()))
	Ans = 0
	for i in range(N + 100):
		for j in range(N):
			if A[j] != j + 1:
				break
		else:
			print(i)
			break
		for j in range(i % 2, N - 1, 2):
			if A[j] > A[j + 1]:
				(A[j], A[j + 1]) = (A[j + 1], A[j])
T = int(input())
for _ in range(T):
	main()


from collections import deque, Counter
from collections import defaultdict as dfd
from bisect import bisect, bisect_left
from math import sqrt, gcd, ceil, factorial
from heapq import heapify, heappush, heappop
MOD = 10 ** 9 + 7
inf = float('inf')
ans_ = []

def nin():
	return int(input())

def ninf():
	return int(file.readline())

def st():
	return input().strip()

def stf():
	return file.readline().strip()

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

def readf():
	return list(map(int, file.readline().strip().split()))

def readfl():
	return list(map(float, input().strip().split()))

def readffl():
	return list(map(float, file.readline().strip().split()))

def solve():
	for _ in range(nin()):
		n = nin()
		arr = read()
		sor = sorted(arr)
		if arr == sor:
			ans_.append(0)
			continue
		c = 0
		for i in range(1, n + 1):
			if i % 2:
				for i in range(0, n, 2):
					if i + 1 < n and arr[i] > arr[i + 1]:
						(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			else:
				for i in range(1, n, 2):
					if i + 1 < n and arr[i] > arr[i + 1]:
						(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			c += 1
			if arr == sor:
				break
		ans_.append(c)
solve()
for i in ans_:
	print(i)


def solve():
	t = int(input())
	for _ in range(t):
		solve_one()

def solve_one():
	n = int(input())
	a = [int(x) for x in input().split()]
	assert len(a) == n
	i = 1
	while True:
		exchanged = False
		if i % 2 != 0:
			for index_1 in range(1, n - 1, 2):
				if f(a, index_1):
					exchanged = True
		else:
			for index_1 in range(2, n, 2):
				if f(a, index_1):
					exchanged = True
		if not exchanged and is_sorted(a):
			print(i - 1)
			return
		i += 1

def f(a, index_1):
	i = index_1 - 1
	if a[i] > a[i + 1]:
		(a[i], a[i + 1]) = (a[i + 1], a[i])
		return True
	return False

def is_sorted(a):
	for i in range(len(a)):
		if a[i] != i + 1:
			return False
	return True
solve()


def IsSort(A):
	return all((A[i] < A[i + 1] for i in range(len(A) - 1)))

def solve(A, n):
	iter = 0
	while not IsSort(A):
		for i in range(iter % 2, n - 1, 2):
			if A[i] > A[i + 1]:
				(A[i], A[i + 1]) = (A[i + 1], A[i])
		iter += 1
	return iter
t = int(input())
for c in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	print(solve(A, n))


from collections import Counter, deque
from math import *
mod = 1000000007

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	l1 = sorted(l)
	count = 0
	while l1 != l:
		check = False
		for i in range(0, n - 1, 2):
			if l[i] > l[i + 1]:
				(l[i], l[i + 1]) = (l[i + 1], l[i])
				check = True
		if True:
			count += 1
		check = False
		if l == l1:
			break
		for i in range(1, n - 1, 2):
			if l[i] > l[i + 1]:
				(l[i], l[i + 1]) = (l[i + 1], l[i])
				check = True
		if True:
			count += 1
	print(count)
for _ in range(int(input())):
	solve()


def solve(arr, n):
	max_sol = 0
	for (i, x) in enumerate(arr):
		sol = abs(x - (i + 1))
		if sol > max_sol:
			max_sol = sol
	return max_sol

def solve_dumb(arr, n):
	if check(arr):
		return 0
	for i in range(n):
		for j in range(n):
			index = 2 * j + i % 2
			if index < n - 1:
				f(arr, 2 * j + i % 2)
		if check(arr):
			return i + 1
	return n

def check(arr):
	for (i, x) in enumerate(arr):
		if i + 1 != x:
			return False
	return True

def f(arr, i):
	if arr[i] > arr[i + 1]:
		tmp = arr[i]
		arr[i] = arr[i + 1]
		arr[i + 1] = tmp
import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
T = int(input().decode().strip())
for t in range(T):
	n = int(input().decode().strip())
	arr = [int(x) for x in input().decode().strip().split(' ')]
	res = solve_dumb(arr, n)
	print(res)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	srt = sorted(arr)
	x = 0
	while not arr == srt:
		for a in range(0, int((n - 1) / 2)):
			if arr[2 * a] > arr[2 * a + 1]:
				one = arr[2 * a]
				two = arr[2 * a + 1]
				arr[2 * a] = two
				arr[2 * a + 1] = one
		x += 1
		if arr == srt:
			break
		for b in range(0, int((n - 1) / 2)):
			if arr[2 * b + 1] > arr[2 * b + 2]:
				one = arr[2 * b + 1]
				two = arr[2 * b + 2]
				arr[2 * b + 1] = two
				arr[2 * b + 2] = one
		x += 1
	print(x)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ctr = 0
	for i in range(n):
		if sorted(l) == l:
			break
		if i % 2 == 0:
			for i in range(0, n - 2, 2):
				if l[i] > l[i + 1]:
					(l[i], l[i + 1]) = (l[i + 1], l[i])
		else:
			for i in range(1, n - 1, 2):
				if l[i] > l[i + 1]:
					(l[i], l[i + 1]) = (l[i + 1], l[i])
		ctr += 1
	print(ctr)


import sys
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, sys.stdin.readline().strip().split()))
	sortedArr = list(range(1, n + 1))
	if sortedArr == arr:
		print(0)
	else:
		srtd = False
		i = 1
		while not srtd:
			srtd = True
			for pos in range(n):
				if i % 2 and (pos + 1) % 2 or (not i % 2 and (not (pos + 1) % 2)):
					if pos < n - 1 and arr[pos] > arr[pos + 1]:
						(arr[pos], arr[pos + 1]) = (arr[pos + 1], arr[pos])
				if srtd and pos != arr[pos] - 1:
					srtd = False
			if not srtd:
				i += 1
		print(i)


from sys import stdin
ii = lambda : int(input())
li = lambda : list(map(int, stdin.readline().strip().split()))
for _ in range(ii()):
	n = ii()
	a = li()
	(a1, c, p) = ([i for i in range(1, n + 1)], 0, 0)
	while a != a1:
		c += 1
		for i in range(p, n, 2):
			try:
				if a[i] > a[i + 1]:
					(a[i], a[i + 1]) = (a[i + 1], a[i])
			except:
				break
		p ^= 1
	print(c)


def solve(length, nums):
	sort = sorted(nums)
	idx = 0
	while True:
		if nums == sort:
			return idx
		idx += 1
		if idx % 2 == 1:
			for i in range(1, length - 1, 2):
				if nums[i - 1] > nums[i]:
					(nums[i - 1], nums[i]) = (nums[i], nums[i - 1])
		else:
			for i in range(2, length, 2):
				if nums[i - 1] > nums[i]:
					(nums[i - 1], nums[i]) = (nums[i], nums[i - 1])
num = int(input())
for n in range(num):
	length = int(input())
	nums = [int(i) for i in input().split()]
	print(solve(length, nums))


from collections import defaultdict
from collections import deque
from sys import stdout
for _ in range(int(input())):
	n = int(input())
	a = [int(i) - 1 for i in input().split()]
	j = 0
	while True:
		isSorted = a[-1] == n - 1
		changed = False
		for i in range(0, n - 1, 2):
			if a[i] > a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
				changed = True
			if a[i] != i or a[i + 1] != i + 1:
				isSorted = False
		if not isSorted:
			j += 1
		else:
			if changed:
				j += 1
			break
		isSorted = a[0] == 0
		changed = False
		for i in range(1, n - 1, 2):
			if a[i] > a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
				changed = True
			if a[i] != i or a[i + 1] != i + 1:
				isSorted = False
		if not isSorted:
			j += 1
		else:
			if changed:
				j += 1
			break
	print(j)


def question1():
	total = int(input())
	arr = list(map(int, input().split()))
	ongoing = 1
	count = 0
	times = 0
	while True:
		if ongoing % 2 == 0:
			j = 1
			found = False
			while j < total:
				if j != total - 1 and arr[j] > arr[j + 1]:
					(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
					found = True
				j += 2
			if found:
				count += 1
				times = 0
			else:
				times += 1
		else:
			found = False
			j = 0
			while j < total:
				if j != total - 1 and arr[j] > arr[j + 1]:
					(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
					found = True
				j += 2
			if found:
				count += 1
				times = 0
			else:
				times += 1
		if times >= 2:
			return ongoing - 2
		ongoing += 1
remained_test_cases = 1
remained_test_cases = int(input())
while remained_test_cases > 0:
	print(question1())
	remained_test_cases -= 1


for s in [*open(0)][2::2]:
	l = [*map(int, s.split())]
	a = sorted(l)
	ans = 0
	while a != l:
		ans += 1
		for i in range(1 - ans & 1, len(l) - 1, 2):
			if l[i] > l[i + 1]:
				(l[i], l[i + 1]) = (l[i + 1], l[i])
	print(ans)


def run():
	t = int(input())
	for i in range(t):
		n = int(input())
		L = []
		L = [int(i) for i in input().split(' ')]
		print(str(ans(L)))

def ans(L, acc=0, i=1):
	while not sortedp(L):
		L = f(L, i)
		acc = acc + 1
		i = 1 - i
	return acc

def sortedp(L):
	x = L[0]
	for i in L[1:]:
		if i != x + 1:
			return False
		x = i
	return True

def f(L, i):
	if L == []:
		return L
	if L[1:] == []:
		return L
	if i == 1:
		k = len(L)
		for i in range(0, k - 1, 2):
			if L[i] > L[i + 1]:
				c = L[i]
				L[i] = L[i + 1]
				L[i + 1] = c
		return L
	else:
		L = [L[0]] + f(L[1:], 1 - i)
		return L

def srt(a, b):
	if a > b:
		return [b, a]
	else:
		return [a, b]
run()


from collections import deque
T = int(input())

def solve():
	n = int(input())
	nums = [int(x) for x in input().split()]
	mask = 0
	i = 1
	for index in range(n):
		if nums[index] == index + 1:
			mask |= 1 << index
	if mask == (1 << n) - 1:
		print(0)
		return
	while True:
		mask = 0
		for index in range(n):
			if index != n - 1:
				if i % 2 != 0 and index % 2 == 0 or (i % 2 == 0 and index % 2 != 0):
					if nums[index] > nums[index + 1]:
						(nums[index], nums[index + 1]) = (nums[index + 1], nums[index])
			if nums[index] == index + 1:
				mask |= 1 << index
		if mask == (1 << n) - 1:
			break
		i += 1
	print(i)
for _ in range(T):
	solve()


import math, bisect, heapq, random, sys, itertools
sys.setrecursionlimit(10 ** 6 + 10)
input = sys.stdin.readline
ints = lambda : list(map(int, input().split()))
p = 10 ** 9 + 7
alpha = 'abcdefghijklmnopqrstuvwxyz'
p2 = [1]
for i in range(30):
	p2.append(p2[i] * 2)
for t in range(int(input())):
	(n,) = ints()
	a = ints()
	b = sorted(a)
	ind = 1
	while a != b:
		if ind % 2:
			for i in range(0, n - 1, 2):
				if a[i] > a[i + 1]:
					(a[i], a[i + 1]) = (a[i + 1], a[i])
		else:
			for i in range(1, n - 1, 2):
				if a[i] > a[i + 1]:
					(a[i], a[i + 1]) = (a[i + 1], a[i])
		ind += 1
	print(ind - 1)


def odd(l):
	for i in range(0, n - 2, 2):
		if l[i] > l[i + 1]:
			k = l[i]
			l[i] = l[i + 1]
			l[i + 1] = k

def even(l):
	for i in range(1, n - 1, 2):
		if l[i] > l[i + 1]:
			k = l[i]
			l[i] = l[i + 1]
			l[i + 1] = k
t = int(input())
while t:
	n = int(input())
	l = [int(x) for x in input().split()]
	a = sorted(l)
	c = 0
	while l != a:
		if c % 2 == 0:
			odd(l)
			c += 1
		else:
			even(l)
			c += 1
	print(c)
	t -= 1


def main():
	test = int(input())
	i = 0
	while i < test:
		num = int(input())
		if num % 2 != 0:
			array = [int(x) for x in input().split(' ')]
			iter_no = strange_sort(num, array)
			print(iter_no)
			i += 1

def strange_sort(n, a):
	ite = 0
	checked = check_sort(n, a)
	if checked == 1:
		ite = 0
	else:
		while checked != 1:
			if ite % 2 != 0:
				start = 1
				ending = n
			else:
				start = 0
				ending = n - 1
			for i in range(start, ending, 2):
				if a[i] > a[i + 1]:
					temp = a[i]
					a[i] = a[i + 1]
					a[i + 1] = temp
			ite += 1
			checked = check_sort(n, a)
	return ite

def check_sort(l, arr):
	check = 1
	for i in range(l - 1):
		if arr[i] > arr[i + 1]:
			check = -1
			break
	return check
main()


for tt in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	cnt = 0
	final = list(range(1, n + 1))
	while True:
		if l == final:
			break
		for i in range(cnt % 2, n, 2):
			if i + 1 < n:
				if l[i] > l[i + 1]:
					(l[i], l[i + 1]) = (l[i + 1], l[i])
		cnt += 1
	print(cnt)


class Liste:

	def __init__(self, x):
		self.x = x
		self.per = 0

	@property
	def n(self):
		return len(self.x)

	@property
	def is_sorted(self):
		x = self.x
		for i in range(1, self.n):
			if x[i - 1] > x[i]:
				return False
		return True

	def change(self, i):
		if self.x[i] > self.x[i + 1]:
			(self.x[i], self.x[i + 1]) = (self.x[i + 1], self.x[i])

def main():
	t = input()
	t = int(t)
	for elet in range(t):
		n = input()
		lis = input()
		lis = lis.split(' ')
		a = [int(ele) for ele in lis]
		app = Liste(a)
		for i in range(10000):
			if app.is_sorted:
				print(i)
				break
			if app.per % 2 == 1:
				val = 1
			else:
				val = 0
			for ind in range(app.n):
				if val > app.n - 2:
					break
				app.change(val)
				val += 2
			app.per += 1
main()


def sortInWave(arr):
	n = len(arr)
	c = 0
	dummy = list(range(1, n + 1))
	i = 0
	while arr != dummy:
		if i % 2 == 0:
			for j in range(0, n - 2, 2):
				if arr[j] > arr[j + 1]:
					(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
		else:
			for j in range(1, n - 1, 2):
				if arr[j] > arr[j + 1]:
					(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
		i += 1
		c += 1
	return c
test = int(input())
for i in range(test):
	nnn = int(input())
	arr = list(map(int, input().split()))
	print(sortInWave(arr))


for _ in range(int(input())):
	a = int(input())
	b = [int(x) for x in input().split()]
	s = sorted(b)
	i = 0
	while b != s and i < a:
		for j in range(i % 2, a - 1, 2):
			if b[j] > b[j + 1]:
				(b[j], b[j + 1]) = (b[j + 1], b[j])
		i += 1
	print(i)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	q = list(map(int, input().split()))
	r = sorted(q)
	if q == r:
		print(0)
		continue
	count = 1
	while q != r:
		if count % 2 == 0:
			for i in range(1, len(q) - 1, 2):
				if q[i] > q[i + 1]:
					(q[i], q[i + 1]) = (q[i + 1], q[i])
		else:
			for i in range(0, len(q) - 1, 2):
				if q[i] > q[i + 1]:
					(q[i], q[i + 1]) = (q[i + 1], q[i])
		count += 1
	print(count - 1)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	an = -1
	c = 0
	xx = sorted(a)
	for i in range(n):
		if a == xx:
			print(i)
			break
		if i % 2 == 0:
			for j in range(0, n, 2):
				if j + 1 < n and a[j + 1] < a[j]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		else:
			for j in range(1, n, 2):
				if j + 1 < n and a[j + 1] < a[j]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
	else:
		print(n)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = sorted(l)
	k = 0
	while l != s:
		if l == s:
			break
		k += 1
		if k % 2 == 0:
			for i in range(1, n - 1, 2):
				if l[i] > l[i + 1]:
					(l[i], l[i + 1]) = (l[i + 1], l[i])
		else:
			for i in range(0, n - 2, 2):
				if l[i] > l[i + 1]:
					(l[i], l[i + 1]) = (l[i + 1], l[i])
	print(k)


def solve(N, nums):
	nums = [0] + nums
	(output, iteration, unsorted) = (0, 1, 1)
	while unsorted:
		unsorted = 0
		for i in range(iteration, N, 2):
			if nums[i] > nums[i + 1]:
				(nums[i], nums[i + 1]) = (nums[i + 1], nums[i])
				unsorted = 1
		if unsorted == 0:
			for i in range(1, N + 1):
				if nums[i] != i:
					unsorted = 1
					break
		iteration = 2 if iteration == 1 else 1
		if unsorted:
			output += 1
	return output
T = int(input())
for i in range(T):
	N = int(input())
	nums = list(map(int, input().split()))
	output = solve(N, nums)
	print(output)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr1 = arr[:]
	arr1.sort()
	i = 1
	c = 0
	while arr != arr1:
		if i % 2 == 1:
			for j in range(0, n - 1, 2):
				if arr[j] > arr[j + 1]:
					(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
		else:
			for j in range(1, n, 2):
				if arr[j] > arr[j + 1]:
					(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
		i += 1
		c += 1
	print(c)


try:
	T = int(input())
	for i in range(T):
		n = int(input())
		L = list(map(int, input().split()))
		cl = 0
		ans = 0
		while True:
			swap = False
			for i in range(cl, len(L), 2):
				if i != len(L) - 1 and L[i] > L[i + 1]:
					(L[i], L[i + 1]) = (L[i + 1], L[i])
					swap = True
			if swap == False:
				for i in range(1, n + 1):
					if i != L[i - 1]:
						swap = True
				if swap == False:
					break
				else:
					ans += 1
			else:
				ans += 1
			if cl == 0:
				cl = 1
			else:
				cl = 0
		print(ans)
except:
	pass


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	while a != sorted(a):
		for i in range(c % 2, n - 1, 2):
			if a[i] > a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
		c += 1
	print(c)


import math
t = int(input())
for w in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = a.copy()
	b.sort()
	count = 0
	while a != b:
		for i in range(n - 1):
			if count % 2 == 0 and i % 2 != 0:
				continue
			if count % 2 != 0 and i % 2 == 0:
				continue
			if a[i] > a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
		count += 1
	print(count)


def check(A):
	for i in range(len(A) - 1):
		if A[i] > A[i + 1]:
			return False
	return True

def f(A, p):
	i = 0 if p % 2 != 0 else 1
	while i < len(A) and i + 1 < len(A):
		if A[i] > A[i + 1]:
			(A[i], A[i + 1]) = (A[i + 1], A[i])
		i += 2
T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	ans = 0
	i = 1
	while not check(A):
		f(A, ans + 1)
		ans += 1
	print(ans)


def isASC(a, n):
	for i in range(1, n + 1):
		if a[i] < a[i - 1]:
			return False
	return True

def f(a, n, i):
	if i < n and a[i] > a[i + 1]:
		(a[i], a[i + 1]) = (a[i + 1], a[i])
t = int(input())
for _ in range(t):
	n = int(input())
	a = [0] + list(map(int, input().split()))
	i = 0
	while True:
		if isASC(a, n):
			break
		i += 1
		if i % 2 == 1:
			for j in range(1, n, 2):
				f(a, n, j)
		else:
			for j in range(2, n, 2):
				f(a, n, j)
	print(i)


t = int(input())
for case in range(t):
	n = int(input())
	A = [int(i) for i in input().split()]
	sa = list(sorted(A))
	iteration = 0
	while A != sa:
		for i in range(iteration % 2, n - 1, 2):
			if A[i] > A[i + 1]:
				(A[i], A[i + 1]) = (A[i + 1], A[i])
				swap = True
		iteration += 1
	print(iteration)


in1 = lambda : int(input())
in2 = lambda : [int(i) for i in input().split()]

def count(ar, n):
	res = 0
	ar_sorted = sorted(ar)
	while True:
		check = True
		for j in range(n):
			if ar[j] != ar_sorted[j]:
				check = False
				break
		if check:
			return res
		if res % 2 == 0:
			i = 0
			while i < n - 2:
				if ar[i] > ar[i + 1]:
					(ar[i], ar[i + 1]) = (ar[i + 1], ar[i])
				i += 2
		else:
			i = 1
			while i < n - 1:
				if ar[i] > ar[i + 1]:
					(ar[i], ar[i + 1]) = (ar[i + 1], ar[i])
				i += 2
		res += 1
for i in range(in1()):
	(n, ar) = (in1(), in2())
	print(count(ar, n))


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	a = f = 0
	while 1:
		for i in range(n):
			if li[i] != i + 1:
				a = a + 1
				f = 0
				break
			else:
				f = 1
		if f == 1:
			break
		elif a % 2 == 1:
			for i in range(0, n - 1, 2):
				if li[i] > li[i + 1]:
					(li[i], li[i + 1]) = (li[i + 1], li[i])
		else:
			for i in range(1, n - 1, 2):
				if li[i] > li[i + 1]:
					(li[i], li[i + 1]) = (li[i + 1], li[i])
	print(a)


def isSorted(vals, n):
	for i in range(n - 1):
		if vals[i] > vals[i + 1]:
			return False
	return True

def comp(vals, i, n):
	if (i + 1) % 2 == 0:
		for i in range(1, n - 1, 2):
			if vals[i] > vals[i + 1]:
				(vals[i], vals[i + 1]) = (vals[i + 1], vals[i])
	elif (i + 1) % 2 != 0:
		for i in range(0, n - 2, 2):
			if vals[i] > vals[i + 1]:
				(vals[i], vals[i + 1]) = (vals[i + 1], vals[i])
for _ in range(int(input())):
	n = int(input())
	vals = [int(i) for i in input().split(' ')]
	iter = 0
	for i in range(n):
		if isSorted(vals, n) is True:
			break
		iter += 1
		comp(vals, i, n)
	print(iter)


n = int(input())

def check(nums):
	if nums == sorted(nums):
		return True
	else:
		return False

def oddChange(nums, length):
	for i in range(1, length, 2):
		if nums[i] > nums[i + 1]:
			(nums[i], nums[i + 1]) = (nums[i + 1], nums[i])
	return nums

def evenChange(nums, length):
	for i in range(0, length - 1, 2):
		if nums[i] > nums[i + 1]:
			(nums[i], nums[i + 1]) = (nums[i + 1], nums[i])
	return nums
for i in range(n):
	length = int(input())
	nums = [int(i) for i in input().split()]
	times = 0
	while True:
		if check(nums) == False:
			times += 1
			nums = evenChange(nums, length)
		else:
			break
		if check(nums) == False:
			times += 1
			nums = oddChange(nums, length)
		else:
			break
	print(times)


from sys import stdin
input = stdin.readline

def answer():
	(ans, i) = (0, 1)
	while a != b:
		if i & 1:
			for j in range(0, n, 2):
				if j + 1 == n:
					break
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		else:
			for j in range(1, n, 2):
				if j + 1 == n:
					break
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		ans += 1
		i += 1
	return ans
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	print(answer())


def isSorted(a):
	return all((a[i] <= a[i + 1] for i in range(len(a) - 1)))

def f(a, i):
	if a[i + 1] < a[i]:
		(a[i + 1], a[i]) = (a[i], a[i + 1])

def iterate(a, i, n):
	m = i % 2
	for i in range(2 - m, n - m, 2):
		f(a, i)

def solve(a, n):
	i = 0
	while not isSorted(a):
		i += 1
		iterate(a, i, n)
	print(i)

def main():
	t = int(input())
	ax = []
	for i in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		a = [0] + a
		ax.append((a, n))
	for (a, n) in ax:
		solve(a, n)
main()


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	c = 0
	itr = 1
	arr_sorted = sorted(arr)
	if len(arr) == 2 and arr[0] == 2:
		c = 1
		arr = sorted(arr)
	while arr != arr_sorted:
		if itr % 2 != 0:
			for j in range(0, len(arr) - 2, 2):
				if arr[j] > arr[j + 1]:
					temp = arr[j]
					arr[j] = arr[j + 1]
					arr[j + 1] = temp
		elif itr % 2 == 0:
			for j in range(1, len(arr) - 1, 2):
				if arr[j] > arr[j + 1]:
					temp = arr[j]
					arr[j] = arr[j + 1]
					arr[j + 1] = temp
		itr += 1
		c += 1
	print(c)


import sys
from bisect import bisect_right as lb
from collections import deque
from queue import PriorityQueue as pq
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
mod = 10 ** 9 + 7
for _ in range(ii()):
	n = ii()
	a = il()
	b = sorted(a)
	if a == b:
		print(0)
		continue
	d = {}
	t = 0
	ans = 0
	for i in range(n):
		d[a[i]] = i
	for j in range(1, 30 * n + 1):
		if j % 2 == 1:
			for i in range(0, n, 2):
				if i == n - 1:
					continue
				if a[i] > a[i + 1]:
					(a[i], a[i + 1]) = (a[i + 1], a[i])
		else:
			for i in range(1, n, 2):
				if a[i] > a[i + 1]:
					(a[i], a[i + 1]) = (a[i + 1], a[i])
		if a == b:
			print(j)
			break


class Solve:

	def __init__(self, l, n):
		self.l = l
		self.n = n
		self.final()

	def final(self):
		sol = sorted(self.l)
		(r, i) = (0, 1)
		while self.l != sol:
			r += 1
			if i & 1:
				for j in range(0, self.n - 1, 2):
					if self.l[j] > self.l[j + 1]:
						(self.l[j], self.l[j + 1]) = (self.l[j + 1], self.l[j])
			else:
				for j in range(1, self.n, 2):
					if self.l[j] > self.l[j + 1]:
						(self.l[j], self.l[j + 1]) = (self.l[j + 1], self.l[j])
			i ^= 1
		print(r)
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	Solve(l, n)


tc = int(input())
answer = []

def helper(i: int, a: list):
	if i % 2 == 0:
		for x in range(1, len(a) - 1, 2):
			if a[x] > a[x + 1]:
				(a[x], a[x + 1]) = (a[x + 1], a[x])
	else:
		for x in range(0, len(a) - 1, 2):
			if a[x] > a[x + 1]:
				(a[x], a[x + 1]) = (a[x + 1], a[x])
for i in range(tc):
	n = int(input())
	a = [int(x) for x in input().split()]
	i = 1
	count = 0
	while sorted(a) != a:
		helper(i, a)
		count += 1
		i += 1
	answer.append(count)
for i in answer:
	print(i)


from cmath import *
from decimal import *
import sys
from tkinter import N
input_ = sys.stdin.readline

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

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

def swap(a, b):
	return (b, a)

def f(a, i):
	if i % 2 == 0:
		for i in range(0, len(a) - 2, 2):
			if a[i] > a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
	else:
		for i in range(1, len(a) - 1, 2):
			if a[i] > a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
	return a

def solves():
	n = int(input())
	ans = 0
	a = _list()
	b = sorted(a)
	i = 0
	while True:
		if a == b:
			break
		a = f(a, i)
		i += 1
		ans += 1
	print(ans)
t = 1
t = int(input())
for _ in range(0, t):
	solves()


t = int(input())
while t > 0:
	n = int(input())
	a = input().split()
	for i in range(n):
		a[i] = int(a[i])
	count = 0
	for i in range(n):
		fl = 1
		for j in range(n - 1):
			if a[j] > a[j + 1]:
				fl = -1
				break
		if fl == 1:
			break
		if i % 2 == 0:
			for j in range(0, n - 1, 2):
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		else:
			for j in range(1, n - 1, 2):
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		count += 1
	print(count)
	t -= 1


def main():
	T = int(input())
	k = 0
	while k < T:
		n = int(input())
		array = list(map(int, input().split(' ')))
		iter = 0
		end_1 = n - 1 if n % 2 == 0 else n
		copy_arr = array[:]
		copy_arr.sort()
		if array == copy_arr:
			print(0)
		else:
			for i in range(n):
				(check_1, check_2) = (False, False)
				if (i + 1) % 2 != 0:
					end_1 = n - 1 if n % 2 != 0 else n
					for p in range(0, end_1, 2):
						if array[p] > array[p + 1]:
							check_1 = True
							(array[p], array[p + 1]) = (array[p + 1], array[p])
				else:
					end_2 = n - 1 if n % 2 == 0 else n
					for q in range(1, end_2, 2):
						if array[q] > array[q + 1]:
							check_2 = True
							(array[q], array[q + 1]) = (array[q + 1], array[q])
				if copy_arr == array:
					iter = i
					break
			print(iter + 1)
		k += 1
main()


import sys

def issorted(vals):
	for idx in range(len(vals) - 1):
		if vals[idx] > vals[idx + 1]:
			break
	else:
		return True
	return False

def swap(idx, vals):
	if vals[idx] > vals[idx + 1]:
		(vals[idx], vals[idx + 1]) = (vals[idx + 1], vals[idx])

def sort(vals):
	iter = 0
	while not issorted(vals):
		iter += 1
		if iter % 2 != 0:
			for idx in range(0, len(vals) - 1, 2):
				swap(idx, vals)
		else:
			for idx in range(1, len(vals), 2):
				swap(idx, vals)
	return iter
t = int(sys.stdin.readline())
while t:
	size = int(sys.stdin.readline())
	vals = [int(i) for i in sys.stdin.readline().split()]
	t -= 1
	print(sort(vals))


import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import bisect_left, bisect_right
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string, heapq as h
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def getInt():
	return int(input())

def getStrs():
	return input().split()

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

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def getBin():
	return list(map(int, list(input())))

def isInt(s):
	return '0' <= s[0] <= '9'

def ceil_(a, b):
	return (a + b - 1) // b
MOD = 10 ** 9 + 7

def solve():
	n = getInt()
	a = getInts()
	count = 0
	sortedA = sorted(a)
	while a != sortedA:
		if count % 2 == 0:
			for i in range(0, n - 1, 2):
				if a[i] > a[i + 1]:
					(a[i], a[i + 1]) = (a[i + 1], a[i])
		else:
			for i in range(1, n - 1, 2):
				if a[i] > a[i + 1]:
					(a[i], a[i + 1]) = (a[i + 1], a[i])
		count += 1
	return count
for _ in range(getInt()):
	print(solve())


import math, io, os, sys

def rindex(lst, value):
	lst.reverse()
	i = lst.index(value)
	lst.reverse()
	return len(lst) - i - 1
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	sor = sorted(a)
	if a == sor:
		print(0)
		continue
	for i in range(1, 999999):
		if i % 2:
			for j in range(0, n - 1, 2):
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		else:
			for j in range(1, n, 2):
				if a[j] > a[j + 1]:
					(a[j], a[j + 1]) = (a[j + 1], a[j])
		if a == sor:
			break
	print(i)


from collections import deque
import heapq
from math import sqrt
import operator
from operator import itemgetter
import sys
import copy
inf_var = 0
if inf_var == 1:
	inf = open('input.txt', 'r')
else:
	inf = sys.stdin
input = inf.readline

def read_one_int():
	return int(input().rstrip('\n'))

def read_one_float():
	return float(input().rstrip('\n'))

def read_list_of_ints():
	res = [int(val) for val in input().rstrip('\n').split(' ')]
	return res

def read_str():
	return input().rstrip()

def main():
	tests = read_one_int()
	for i in range(tests):
		n = read_one_int()
		elements = read_list_of_ints()
		elements_sorted = sorted(elements)
		res = 0
		while elements != elements_sorted:
			res += 1
			if res % 2:
				st = 0
				end = n - 1
			else:
				st = 1
				end = n
			for i in range(st, end, 2):
				if elements[i] > elements[i + 1]:
					(elements[i], elements[i + 1]) = (elements[i + 1], elements[i])
		print(res)
main()


def bubbleSort(n, arr):
	count = 0
	k = 0
	flag = False
	if arr == sorted(arr):
		return 0
	for i in range(n):
		if arr == sorted(arr):
			break
		else:
			count += 1
		if i % 2 == 0:
			k = 0
		else:
			k = 1
		for j in range(k, n - 1, 2):
			if arr[j] > arr[j + 1]:
				(arr[j], arr[j + 1]) = (arr[j + 1], arr[j])
	return count
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	res = bubbleSort(n, arr)
	print(res)


t = int(input())

def f(i, arr):
	if arr[i] > arr[i + 1]:
		c = arr[i]
		arr[i] = arr[i + 1]
		arr[i + 1] = c
	return arr
for _ in range(t):
	n = int(input())
	sorted = []
	for o in range(n + 1):
		sorted.append(o)
	arr = [int(x) for x in input().split()]
	arr.insert(0, 0)
	count = 0
	r = 1
	while (arr == sorted) == False:
		count = count + 1
		if r % 2 == 1:
			for i in range(1, (n - 1) // 2 + 1):
				arr = f(2 * i - 1, arr)
			r = r + 1
			continue
		else:
			for i in range(1, (n - 1) // 2 + 1):
				arr = f(2 * i, arr)
			r = r + 1
			continue
	print(count)


t = int(input())
for task in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	res = 0
	while True:
		for i in range(n):
			if i != a[i] - 1:
				break
		else:
			break
		res += 1
		shift = 1 - res % 2
		for j in range(shift, n - 1, 2):
			if a[j] > a[j + 1]:
				(a[j], a[j + 1]) = (a[j + 1], a[j])
	print(res)


from collections import defaultdict

def solve():
	test_case = int(input())
	while test_case > 0:
		n = int(input())
		arr = list(map(int, input().split()))
		answer = sorted(arr)
		iteration = 1
		while arr != answer:
			if iteration % 2 == 1:
				for i in range(0, len(arr) - 2, 2):
					if arr[i] > arr[i + 1]:
						(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			else:
				for i in range(1, len(arr) - 1, 2):
					if arr[i] > arr[i + 1]:
						(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
			iteration += 1
		print(iteration - 1)
		test_case -= 1
solve()