You are given a permutation $p$ of length $n$ (a permutation of length $n$ is an array of length $n$ in which each integer from $1$ to $n$ occurs exactly once).

You can perform the following operation any number of times (possibly zero):

choose two different elements $x$ and $y$ and erase them from the permutation;

insert the minimum of $x$ and $y$ into the permutation in such a way that it becomes the first element;

insert the maximum of $x$ and $y$ into the permutation in such a way that it becomes the last element.

For example, if $p = [1, 5, 4, 2, 3]$ and we want to apply the operation to the elements $3$ and $5$, then after the first step of the operation, the permutation becomes $p = [1, 4, 2]$; and after we insert the elements, it becomes $p = [3, 1, 4, 2, 5]$.

Your task is to calculate the minimum number of operations described above to sort the permutation $p$ in ascending order (i. e. transform $p$ so that $p_1 < p_2 < \dots < p_n$).


-----Input-----

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

The first line of the test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in the permutation.

The second line of the test case contains $n$ distinct integers from $1$ to $n$ — the given permutation $p$.

The sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case, output a single integer — the minimum number of operations described above to sort the array $p$ in ascending order.


-----Examples-----

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


-----Note-----

In the first example, you can proceed as follows:

in the permutation $p = [1, 5, 4, 2, 3]$, let's choose the elements $4$ and $2$, then, after applying the operation, the permutation becomes $p = [2, 1, 5, 3, 4]$;

in the permutation $p = [2, 1, 5, 3, 4]$, let's choose the elements $1$ and $5$, then, after applying operation, the permutation becomes $p = [1, 2, 3, 4, 5]$.

Difficulty: MEDIUM
Tags: Sorting

Amortized analysis

Greedy algorithms

Complete search

Mathematics
Skill types: Complete search

Sorting

Amortized analysis

Greedy algorithms

Starter code:

Solutions:
import math
from sys import stdin, stdout
input = stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m1 = math.ceil(n / 2)
	t = []
	flag = False
	s = 0
	for i in a:
		if not t:
			if i <= m1:
				t.append(i)
			if i == m1:
				flag = True
			continue
		if i > t[-1] and i <= m1:
			if i == m1:
				flag = True
			t.append(i)
			if t[-1] - t[-2] > 1:
				s = len(t) - 1
		if flag and i - t[-1] == 1:
			t.append(i)
	maxi = max(t[s] - 1, n - t[-1])
	if maxi > m1:
		print(m1)
	else:
		print(maxi)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
t = inp()
for _ in range(t):
	n = inp()
	arr = inlt()
	Sorted = [-1] * (n + 1)
	for index in range(n):
		Sorted[arr[index]] = index
	left = (n + 1) // 2
	right = (n + 2) // 2
	while left > 0 and (left == right or (Sorted[left] < Sorted[left + 1] and Sorted[right - 1] < Sorted[right])):
		left -= 1
		right += 1
	print(left)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input()) + 1
	a = [0 for i in range(n)]
	inp = list(map(int, input().split()))
	for i in range(len(inp)):
		a[inp[i]] = i
	l = n // 2
	r = (n + 1) // 2
	while l > 0 and (l == r or (a[l + 1] > a[l] and a[r - 1] < a[r])):
		l -= 1
		r += 1
	print((n - r + l + 1) // 2)


for i in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	l = n // 2 + 1
	for i in nums:
		if i == l:
			l += 1
	nums.reverse()
	r = 0
	if n // 2 == 0:
		r = n // 2
	else:
		r = n // 2 + 1
	for i in nums:
		if i == r:
			r -= 1
	print(min(max(n - l + 1, r), n // 2))


def solve():
	n = int(input())
	v1 = list(map(int, input().split()))
	v2 = [0] * (n + 1)
	for x in v1:
		v2[x] = v2[x - 1] + 1
	for i in range(1, (n + 1) // 2 + 1):
		ok = n - 2 * (i - 1)
		if v2[n - i + 1] >= ok:
			print(i - 1)
			return
	print((n + 1) // 2)
t = int(input())
for _ in range(t):
	solve()


def main():
	n = int(input())
	arr = list(map(int, input().split()))
	if n % 2 == 1:
		m1 = (n + 1) // 2
		i1 = arr.index(m1)
		l = m1 - 1
		r = m1 + 1
		for i in range(i1):
			if l == arr[i1 - i - 1]:
				l = l - 1
		for i in range(n - 1 - i1):
			if r == arr[i1 + i + 1]:
				r = r + 1
		cnt = min(m1 - l, r - m1)
		print((n - 2 * cnt + 1) // 2)
	else:
		m1 = n // 2
		m2 = m1 + 1
		i1 = arr.index(m1)
		i2 = arr.index(m2)
		if i1 > i2:
			print(m1)
			return
		l = m1 - 1
		r = m2 + 1
		for i in range(i1):
			if l == arr[i1 - i - 1]:
				l = l - 1
		for i in range(n - 1 - i2):
			if r == arr[i2 + i + 1]:
				r = r + 1
		cnt = min(m1 - l, r - m2)
		print((n - 2 * cnt) // 2)
t = int(input())
while t > 0:
	t -= 1
	main()


for _ in range(int(input())):
	z = int(input())
	t = list(map(int, input().split()))
	q = [-1] * (z + 1)
	for i in range(z):
		q[t[i]] = i
	l = (z + 1) // 2
	r = (z + 2) // 2
	while l > 0 and (l == r or (q[l] < q[l + 1] and q[r - 1] < q[r])):
		l -= 1
		r += 1
	print(l)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = [-1] * (n + 1)
	for i in range(n):
		m[a[i]] = i
	l = (n + 1) // 2
	r = (n + 2) // 2
	while l > 0 and (l == r or (m[l] < m[l + 1] and m[r - 1] < m[r])):
		l -= 1
		r += 1
	print(l)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	pos = [0] * (n + 1)
	for i in range(n):
		pos[a[i]] = i
	i = (n + 1) // 2
	j = (n + 2) // 2
	while i > 0 and i == j or (pos[i] < pos[i + 1] and pos[j - 1] < pos[j]):
		i -= 1
		j += 1
	print(i)


import sys
input = sys.stdin.readline
t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = [0] * (n + 1)
	for i in range(n):
		b[a[i]] = i
	lr = (n + 1) // 2
	hr = (n + 2) // 2
	l = (n - 1) // 2
	h = (n + 4) // 2
	ans = 0
	if b[lr] > b[hr]:
		ans = 1
	while l >= 1 and h <= n:
		if b[l] < b[l + 1] <= b[h - 1] < b[h]:
			pass
		else:
			ans += 1
			b[l] = 0
			b[h] = n - 1
		l -= 1
		h += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	p = [int(x) for x in input().split()]
	if n % 2 == 1:
		mid = n // 2 + 1
		mid_ind = p.index(mid)
		(before, after) = (0, 0)
		(tmp1, tmp2) = (mid - 1, mid + 1)
		for i in range(mid_ind, -1, -1):
			if p[i] == tmp1:
				tmp1 -= 1
				before += 1
		for i in range(mid_ind, n):
			if p[i] == tmp2:
				tmp2 += 1
				after += 1
		res = n // 2 - min(before, after)
		print(res)
	else:
		(mid1, mid2) = (n // 2, n // 2 + 1)
		(mid1_ind, mid2_ind) = (p.index(mid1), p.index(mid2))
		if mid2_ind < mid1_ind:
			print(n // 2)
			continue
		(before, after) = (1, 1)
		(tmp1, tmp2) = (mid1 - 1, mid2 + 1)
		for i in range(mid1_ind - 1, -1, -1):
			if p[i] == tmp1:
				tmp1 -= 1
				before += 1
		for i in range(mid2_ind + 1, n):
			if p[i] == tmp2:
				tmp2 += 1
				after += 1
		res = n // 2 - min(before, after)
		print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	m = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		my_set = set()
		my_set.add(m[0])
		positions = [0] * n
		positions[0] = 1
		for x in m[1:]:
			if x - 1 in my_set:
				positions[x - 1] = 1
			my_set.add(x)
		if n % 2 == 1 and positions[n // 2] == 0:
			print(n // 2)
			continue
		if n % 2 == 0:
			(i, j) = (n // 2, n // 2)
		else:
			(i, j) = (n // 2, n // 2 + 1)
		while i > 0:
			if positions[i] == 0 or positions[j] == 0:
				break
			i -= 1
			j += 1
		print(i)


for _ in range(int(input())):
	num = int(input())
	X = list(map(int, input().split()))
	m = [-1] * (num + 1)
	for i in range(num):
		m[X[i]] = i
	L = (num + 1) // 2
	R = (num + 2) // 2
	while L > 0 and (L == R or (m[L] < m[L + 1] and m[R - 1] < m[R])):
		L -= 1
		R += 1
	print(L)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	pos = dict()
	for i in range(n):
		pos[a[i]] = i
	cnt = n // 2
	(l, r) = ((n + 2) // 2, (n + 1) // 2)
	while 1 < l and r < n:
		if pos[l - 1] < pos[l] and pos[r] < pos[r + 1]:
			l -= 1
			r += 1
			cnt -= 1
		else:
			break
	print(cnt)


def getint():
	return int(input())

def getfloat():
	return float(input())

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

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

def getans(n, lis):
	if n % 2 == 1:
		indl = lis.index(n // 2 + 1)
		indr = indl
		tarl = n // 2
		tarr = tarl + 2
		found = 1
	else:
		for i in range(len(lis)):
			if lis[i] == n // 2:
				indl = i
				break
			if lis[i] == n // 2 + 1:
				return n // 2
		indr = lis.index(n // 2 + 1, indl)
		tarl = n // 2 - 1
		tarr = n // 2 + 2
		found = 2
	c1 = 0
	c2 = 0
	while indl >= 0:
		if tarl == lis[indl]:
			tarl -= 1
			c1 += 1
		indl -= 1
	while indr < len(lis):
		if tarr == lis[indr]:
			tarr += 1
			c2 += 1
		indr += 1
	return (n - found) // 2 - min(c1, c2)
T = getint()
for i in range(T):
	n = getint()
	lis = getints()
	print(getans(n, lis))


import math
t = int(input())
for _ in range(t):
	n = int(input())
	p = [int(x) for x in input().split()]
	m = math.ceil(n / 2)
	l = -1
	r = -1
	c = False
	moves = math.floor(n / 2)
	if n % 2 == 1:
		if n == 1:
			moves = 0
		elif p.index(m - 1) < p.index(m) and p.index(m + 1) > p.index(m):
			l = m - 1
			r = m + 1
			moves -= 1
			c = True
	else:
		l = n / 2
		r = l + 1
		if p.index(l) < p.index(r):
			moves -= 1
			c = True
	if c and moves > 0:
		r_count = 0
		l_count = 0
		for x in p[p.index(r):]:
			if x - 1 == r:
				r += 1
				r_count += 1
		v = p[:p.index(l) + 1]
		v.reverse()
		for x in v:
			if x + 1 == l:
				l -= 1
				l_count += 1
		moves -= min(l_count, r_count)
	print(moves)


tests1 = int(input())
for _ in range(tests1):
	n1 = int(input())
	pos = [0] * n1
	m = list(map(int, input().split()))
	for (i, x) in enumerate(m, 1):
		pos[x - 1] = i
	if n1 % 2 == 0:
		(i, j) = (n1 // 2 - 1, n1 // 2)
	else:
		(i, j) = (n1 // 2 - 1, n1 // 2 + 1)
	while i > -1:
		if pos[i] > pos[i + 1] or pos[j] < pos[j - 1]:
			break
		i -= 1
		j += 1
	print(i + 1)


import math
for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	m = math.ceil(n / 2)
	m_it = -1
	for i in range(len(p)):
		if p[i] == m:
			m_it = i
	m_i = m + 1
	c_i = 0
	for i in range(m_it, len(p)):
		if p[i] == m_i:
			c_i += 1
			m_i += 1
	m_d = m - 1
	c_d = 0
	for i in range(m_it, -1, -1):
		if p[i] == m_d:
			c_d += 1
			m_d -= 1
	c_i = n - m - c_i
	c_d = m - 1 - c_d
	print(min(c_i, c_d) + abs(c_i - c_d))


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	pos = [0] * (n + 1)
	for i in range(n):
		pos[p[i]] = i
	l = (n + 1) // 2
	r = (n + 2) // 2
	while l > 0 and (l == r or (pos[l] < pos[l + 1] and pos[r - 1] < pos[r])):
		l -= 1
		r += 1
	print((n - r + l + 1) // 2)


def f(n, l):
	if n % 2 == 0:
		max = n // 2 + 1
		max_new = max
		min_new = max
		ind = l.index(max)
		for i in range(ind + 1, n):
			if l[i] == max_new + 1:
				max_new = max_new + 1
		for j in range(ind - 1, -1, -1):
			r = l[j]
			if l[j] == min_new - 1:
				min_new = min_new - 1
		k = min(max - min_new, max_new - max + 1)
		print(n // 2 - k)
	else:
		max = n // 2 + 1
		max_new = max
		min_new = max
		ind = l.index(max)
		for i in range(ind + 1, n):
			if l[i] == max_new + 1:
				max_new = max_new + 1
		for j in range(ind - 1, -1, -1):
			r = l[j]
			if l[j] == min_new - 1:
				min_new = min_new - 1
		k = min(max_new - max, max - min_new)
		print(n // 2 - k)
for t in range(int(input())):
	inp = int(input())
	inp1 = list(map(int, input().split(' ')))
	f(inp, inp1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	pos = [0] * (n + 2)
	pos[-1] = n + 1
	for i in range(n):
		pos[a[i]] = i + 1
	res = (n + 1) // 2
	(l, r) = ((n + 1) // 2, (n + 2) // 2)
	while l > 0 and (l == r or (pos[l] < pos[l + 1] and pos[r - 1] < pos[r])):
		r += 1
		l -= 1
		res -= 1
	print(res)


import math
k = int(input())
res = []
while k > 0:
	n = int(input())
	temp = input().split(' ')
	arr = []
	for num in temp:
		arr.append(int(num))
	total = math.ceil(n / 2)
	left_mid = 0
	right_mid = 0
	(left, right) = (-1, -1)
	if n % 2 == 0:
		left_mid = int(n / 2)
		right_mid = left_mid + 1
	else:
		left_mid = int(n / 2) + 1
		right_mid = left_mid
	for i in range(len(arr)):
		if arr[i] == left_mid:
			left = i
		if arr[i] == right_mid:
			right = i
	if left <= right:
		total -= 1
		left_arrange = 0
		left_next = left_mid
		while left >= 0:
			if arr[left] == left_next:
				left_next -= 1
			left -= 1
		right_arrange = 0
		right_next = right_mid
		while right < n:
			if arr[right] == right_next:
				right_next += 1
			right += 1
		minus = min(left_mid - left_next - 1, right_next - right_mid - 1)
		total -= minus
	res.append(total)
	k -= 1
for x in res:
	print(x)


def isSorted(arr, ignore, idx1, idx2):
	j = idx1
	for i in range(idx1 + 1, idx2 + 1):
		if i in ignore:
			continue
		if arr[j] + 1 == arr[i]:
			j = i
		else:
			return False
	return True

def main(arr):
	numToIdx = {}
	for (i, num) in enumerate(arr):
		numToIdx[num] = i
	(n1, n2) = (1, len(arr))
	n = len(arr)
	ans = 0
	seen = set()
	while n > 1:
		idx1 = numToIdx[n1]
		idx2 = numToIdx[n2]
		if idx1 < idx2 and isSorted(arr, seen, idx1, idx2):
			return ans
		seen.add(idx1)
		seen.add(idx2)
		n1 += 1
		n2 -= 1
		ans += 1
		n -= 2
	return ans
i = int(input())
for _ in range(i):
	n = int(input())
	arr = list(map(int, input().split()))
	print(main(arr))


from collections import defaultdict

def d():
	return 0
for __ in range(int(input())):
	n = int(input())
	permutation = list(map(int, input().split()))
	s = sorted(permutation)
	dict = defaultdict(d)
	if s == permutation:
		print(0)
	else:
		for i in range(len(permutation)):
			dict[permutation[i]] = i
		for k in range(1, n):
			flag = True
			for m in range(k + 1, n - k):
				if dict[m] < dict[m + 1]:
					continue
				else:
					flag = False
					break
			if flag:
				print(k)
				break


from collections import defaultdict
import math
for j in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	for i in range(n):
		d[l[i]] = i
	if n % 2 == 0:
		mid = n // 2
		i = 0
		dif = 1
	else:
		mid = n // 2 + 1
		i = 1
		dif = 0
	count = 0
	while i < mid:
		s = mid - i
		e = mid + i + dif
		if d[s] < d[e] and d[s] < d[s + 1] and (d[e] > d[e - 1]):
			count += 1
		else:
			break
		i += 1
	print(n // 2 - count)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	mp = {}
	for i in range(len(arr)):
		mp[arr[i]] = i
	ans = (n + 1) // 2
	(prel, prer) = (mp[(n + 1) // 2], mp[n + 1 - (n + 1) // 2])
	for i in range((n + 1) // 2, 0, -1):
		l = mp[i]
		r = mp[n + 1 - i]
		if l <= r and l <= prel and (r >= prer):
			ans -= 1
			prel = l
			prer = r
			continue
		else:
			break
	print(ans)


t = int(input())
for t1 in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	dict = {}
	for i in range(n):
		dict[p[i]] = i + 1
	if n % 2 == 1:
		mid = (n + 1) // 2
		tmp = dict[mid]
		rcount = 0
		while mid < n and tmp < dict[mid + 1]:
			tmp = dict[mid + 1]
			mid += 1
			rcount += 1
		mid = (n + 1) // 2
		tmp = dict[mid]
		lcount = 0
		while mid > 1 and tmp > dict[mid - 1]:
			tmp = dict[mid - 1]
			lcount += 1
			mid -= 1
		ans = n - 2 * min(lcount, rcount) - 1
		print((ans + 1) // 2)
		continue
	else:
		lmid = n // 2
		rmid = lmid + 1
		if dict[lmid] < dict[rmid]:
			rcount = 0
			lcount = 0
			tmp = dict[rmid]
			while rmid < n and tmp < dict[rmid + 1]:
				tmp = dict[rmid + 1]
				rmid += 1
				rcount += 1
			tmp = dict[lmid]
			while lmid > 1 and tmp > dict[lmid - 1]:
				tmp = dict[lmid - 1]
				lmid -= 1
				lcount += 1
			ans = n - 2 * min(lcount, rcount) - 2
			print((ans + 1) // 2)
			continue
		else:
			print((n + 1) // 2)
			continue


t = int(input())
while t > 0:
	n = int(input())
	tab = list(map(int, input().split()))
	if n == 1:
		print(0)
		t -= 1
		continue
	idx = [0] * n
	for i in range(n):
		idx[tab[i] - 1] += i
	m = n // 2
	cont = False
	if n % 2 == 0:
		a = n // 2
		b = a + 1
		if idx[a - 1] < idx[b - 1]:
			m -= 1
			old_a = a
			old_b = b
			a = a - 1
			b = b + 1
			cont = True
	else:
		a = n // 2
		b = a + 1
		c = b + 1
		if idx[a - 1] < idx[b - 1] and idx[b - 1] < idx[c - 1]:
			m -= 1
			old_a = a
			old_b = c
			a = a - 1
			b = c + 1
			cont = True
	if cont:
		while a >= 1 and b <= n and (idx[a - 1] < idx[old_a - 1]) and (idx[b - 1] > idx[old_b - 1]):
			m -= 1
			old_a = a
			old_b = b
			a = a - 1
			b = b + 1
	print(m)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	li = list(map(int, input().split()))
	placement_li = [0 for i in range(n)]
	for j in range(1, n + 1):
		placement_li[li[j - 1] - 1] = j
	total = int((n + 1) / 2)
	if n == 1:
		print(0)
		continue
	elif n % 2 == 0:
		left = int(n / 2)
		right = int(n / 2) + 1
	else:
		left = right = int((n + 1) / 2)
	while left >= 1 and (left == right or (placement_li[left - 1] < placement_li[left] and placement_li[right - 2] < placement_li[right - 1])):
		left -= 1
		right += 1
		total -= 1
	print(total)


T = int(input())
for t in range(T):
	n = int(input())
	p = [int(i) for i in input().split()]
	pos = [0 for i in range(n)]
	for (it, el) in enumerate(p):
		pos[el - 1] = it
	ans = (n + 1) // 2
	l = (n + 1) // 2 - 1
	r = (n + 2) // 2 - 1
	while l >= 0 and (l == r or (pos[l] < pos[l + 1] and pos[r] > pos[r - 1])):
		ans -= 1
		l -= 1
		r += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [-1]
	d = dict()
	a = a + list(map(int, input().split()))
	for i in range(1, n + 1):
		d[a[i]] = i
	bef = n // 2
	aft = (n + 1) // 2 + 1
	condtn = False
	while not condtn and bef >= 1 and (aft <= n):
		if d[bef] > d[aft]:
			condtn = True
			break
		if bef != aft - 1:
			if d[bef] > d[bef + 1] or d[aft] < d[aft - 1]:
				condtn = True
				break
		bef -= 1
		aft += 1
	print(bef)


import math
for _ in range(int(input())):
	n = int(input())
	pos = []
	for i in range(n + 1):
		pos.append(0)
	arr = [int(x) for x in input().split()]
	arr = [0] + arr
	for i in range(1, n + 1):
		pos[arr[i]] = i
	if n % 2 == 0:
		middle = n // 2
		ans = 0
		for i in range(middle):
			if pos[middle - i] < pos[middle + 1 + i]:
				if i == 0:
					continue
				if pos[middle - i] < pos[middle - i + 1] and pos[middle + i + 1] > pos[middle + i]:
					continue
				else:
					ans = middle - i
					break
			else:
				ans = middle - i
				break
		print(ans)
	else:
		if n == 1:
			print(0)
			continue
		middle = n // 2 + 1
		if pos[middle - 1] < pos[middle] < pos[middle + 1]:
			pass
		else:
			ans = middle - 1
			print(ans)
			continue
		ans = 0
		for i in range(2, middle, 1):
			if pos[middle - i] < pos[middle + i]:
				if pos[middle - i] < pos[middle - i + 1] and pos[middle + i] > pos[middle + i - 1]:
					continue
				else:
					ans = middle - i
					break
			else:
				ans = middle - i
				break
		print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	idx = [-1 for _ in range(n + 1)]
	final = 0
	for (x, i) in enumerate(arr):
		idx[i] = x
	for i in range(1, n):
		if idx[i] > idx[i + 1]:
			final = max(final, min(i, n - i))
	print(final)


def freq(arr):
	n = len(arr)
	fr = {i: -1 for i in range(n)}
	for i in range(n):
		fr[arr[i] - 1] = i
	return fr

def sol():
	n = int(input())
	p = [int(i) for i in input().split()]
	a = [i - 1 for i in p]
	mid = n // 2
	fr = freq(p)
	(ahead, back) = (0, 0)
	fg = mid
	for i in range(fr[mid], n):
		if a[i] == fg + 1:
			ahead += 1
			fg = a[i]
	fg = mid
	for i in range(fr[mid] - 1, -1, -1):
		if a[i] == fg - 1:
			fg = a[i]
			back += 1
	if n % 2 != 0:
		print(n // 2 - min(ahead, back))
	else:
		print(n // 2 - min(ahead + 1, back))
t = int(input())
for i in range(t):
	sol()


from collections import defaultdict

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

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

def S():
	return input()
for _ in range(N()):
	n = N()
	f = True
	d = defaultdict(int)
	if 'codeforces' == 28226329:
		print('Tanmay')
	a = A()
	if n == 1:
		print(0)
		continue
	for i in range(n):
		if i + 1 != a[i]:
			f = False
		d[a[i]] = i
	if f:
		print(0)
		continue
	l = c = (n + 1) // 2
	r = l
	if n % 2 == 0:
		r += 1
	while l > 0 and r <= n and (d[r] >= d[l]):
		r += 1
		c -= 1
		l -= 1
		if d[l] >= d[l + 1] or d[r] <= d[r - 1]:
			break
	print(c)


def min_max_sort(n, p):
	k = n >> 1
	while k and p[k] < p[k + 1] and (p[n - k + 1] > p[n - k]):
		k -= 1
	print(k)
t = eval(input())
for _ in range(t):
	n = eval(input())
	p = [0] * (n + 1)
	x = list(map(int, input().split()))
	for i in range(1, n + 1):
		p[x[i - 1]] = i
	min_max_sort(n, p)


t = int(input())
while t:
	t -= 1
	n = int(input())
	nums = list(map(int, input().split()))
	dp = [0] * (n + 1)
	ans = n // 2
	for x in nums:
		dp[x] = dp[x - 1] + 1
		ans = min(ans, max(x - dp[x], n - x))
	print(ans)


for t in range(int(input())):
	n = int(input())
	a = [(i, int(c)) for (i, c) in enumerate(input().split())]
	a.sort(key=lambda x: x[1])
	ans = n
	start = 0
	for i in range(1, n):
		if a[i][0] < a[i - 1][0]:
			ans = min(ans, max(start, n - i))
			start = i
	ans = min(ans, max(start, 0))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	cont_memo = {arr[0]: 1}
	index = {i: idx for (idx, i) in enumerate(arr)}
	index[0] = float('inf')
	for idx in range(1, n):
		i = arr[idx]
		cont_memo[i] = 1
		if index[i - 1] < index[i]:
			cont_memo[i] += cont_memo[i - 1]
	res = float('inf')
	for i in cont_memo:
		last = n - i
		first = i - cont_memo[i]
		res = min(res, max(last, first))
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	p = [0] * (n + 1)
	for i in range(n):
		p[a[i]] = i
	k = [0] * (n + 1)
	k[n] = 1
	for i in range(n - 1, 0, -1):
		if p[i] < p[i + 1]:
			k[i] = k[i + 1] + 1
		else:
			k[i] = 1
	res = n
	for i in range(1, n + 1):
		res = min(res, max(i - 1, n - (i + k[i] - 1)))
	print(res)


import sys
import math
import itertools

def ok(a, x):
	b = []
	n = len(a)
	for i in a:
		if i > x and i < n - x + 1:
			b.append(i)
	return b == sorted(b)

def solution():
	n = int(input())
	a = list(map(int, input().split()))
	r = n // 2
	l = -1
	while r - l > 1:
		m = (r + l) // 2
		if ok(a, m):
			r = m
		else:
			l = m
	print(r)
t = int(input())
for i in range(t):
	solution()


import sys

def check(a):
	holder = []
	for i in numbers:
		if i > a and i <= n - a:
			holder.append(i)
	if holder == []:
		return True
	return all((a <= b for (a, b) in zip(holder, holder[1:])))
t = int(input())
for i in range(t):
	n = int(input())
	numbers = [*map(int, input().split())]
	left = 0
	right = n // 2 + 1
	while left < right:
		mid = (left + right) // 2
		if check(mid):
			right = mid
		else:
			left = mid + 1
	print(left)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	l = 0
	r = n // 2
	while l < r:
		mid = (l + r) // 2
		ele = -1
		flag = False
		for i in range(n):
			if a[i] > mid and a[i] < n - mid + 1:
				if a[i] <= ele:
					flag = True
					break
				else:
					ele = a[i]
		if l == r - 1:
			if flag == False:
				print(l)
				return
			else:
				print(r)
				return
		elif flag == False:
			r = mid
		else:
			l = mid + 1
	print(l)
t = int(input())
for _ in range(t):
	solve()


import sys

def check(n, data):
	if n * 2 + 1 >= len(data):
		return True
	order = dict()
	for (idx, el) in enumerate(data):
		order[el] = idx
	begin = n + 1
	end = len(data) - n
	for el in range(begin, end):
		if order[el] > order[el + 1]:
			return False
	return True

def solution():
	n = int(input())
	data = list(map(int, input().split()))
	left = -1
	right = n
	while right - left > 1:
		mid = (left + right + 1) // 2
		if check(mid, data):
			right = mid
		else:
			left = mid
	print(right)
t = int(input())
for _ in range(t):
	solution()


import sys
t = int(sys.stdin.readline())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	ans = n // 2
	l = 0
	r = n // 2 + 1
	while True:
		if r < l:
			break
		mid = (l + r) // 2
		vec = [0] * (n + 1)
		st = mid + 1
		en = n - mid
		er = 0
		for j in lst:
			if j > st and j <= en and (vec[j - 1] == 0):
				er += 1
				break
			vec[j] += 1
		if er > 0:
			l = mid + 1
		else:
			r = mid - 1
			ans = min(ans, mid)
	print(ans)


def sor(a):
	if len(a) == 0:
		return True
	last = a[0] - 1
	for j in a:
		if j != last + 1:
			return False
		last = j
	return True
t = int(input())
for _ in range(t):
	n = int(input())
	(*a,) = map(int, input().split())
	ans = 0
	nado = True
	ma = n + 1
	mi = 0
	L = 0
	R = n // 2 + n % 2
	while L + 1 < R:
		x = (L + R) // 2
		b = []
		for j in a:
			if mi + x < j < ma - x:
				b += [j]
		if not sor(b):
			L = x
		else:
			R = x
	x = L
	b = []
	for j in a:
		if mi + x < j < ma - x:
			b += [j]
	if not sor(b):
		L += 1
	print(L)