Chef considers a permutation P of \{1, 2, 3, \dots, N\} End Sorted if and only if P_{1} = 1 and P_{N} = N.

Chef is given a permutation P.

In one operation Chef can choose any index i \ (1 ≤ i ≤ N-1) and swap P_{i} and P_{i+1}. Determine the minimum number of operations required by Chef to make the permutation P End Sorted.

Note: An array P is said to be a permutation of \{1, 2, 3, \dots, N\} if P contains each element of \{1, 2, 3, \dots, N\} exactly once. 

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains a single integer N, denoting the length of the permutation P.
- The second line contains N space-separated integers P_{1}, P_{2}, P_{3}, \ldots, P_{N}, denoting the permutation P.

------ Output Format ------ 

For each test case, output minimum number of operations required by Chef to make the permutation P End Sorted.

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

$1 ≤ T ≤ 1000$
$2 ≤ N ≤ 10^{5}$
$P$ is a permutation of $\{1, 2, 3, \dots N\}$
- The sum of $N$ over all test cases does not exceed $3 \cdot 10^{5}$.

----- Sample Input 1 ------ 
4
4
1 3 2 4
3
3 2 1
2
2 1
3
2 1 3

----- Sample Output 1 ------ 
0
3
1
1

----- explanation 1 ------ 
Test case $1$: $P$ is already End Sorted.

Test case $2$: $P$ can be made End Sorted using $3$ operations as follows: $[3, 2, 1] \to [\textcolor{red}{2, 3}, 1] \to [2, \textcolor{red}{1, 3}] \to [\textcolor{red}{1, 2}, 3]$. It can be shown that achieving this in fewer than $3$ moves is impossible.

Test case $3$: $P$ can be made End Sorted using one operation, by swapping $1$ and $2$.

Test case $4$: $P$ can be made End Sorted using one operation, by swapping $1$ and $2$.

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	loc1 = p.index(1)
	locn = p.index(n)
	print(n - 1 - locn + loc1 - int(loc1 > locn))


for i in range(int(input())):
	N = int(input())
	array = list(map(int, input().split()))
	i1 = array.index(1)
	iN = array.index(N)
	if i1 < iN:
		print(i1 + (N - 1) - iN)
	else:
		print(i1 + (N - 1) - iN - 1)


t = int(input())
for x in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	loc1 = p.index(1)
	locn = p.index(n)
	print(n - 1 - locn + loc1 - int(loc1 > locn))


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))[:n]
	ans = len(p) - 1 - p.index(max(p))
	p.remove(max(p))
	ans += p.index(min(p))
	print(ans)


for i in range(int(input())):
	n = int(input())
	A = [int(n) for n in input().split()]
	a = A.index(1)
	b = A.index(n)
	ans = a + n - b - 1
	if b < a:
		ans -= 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = l.index(1)
	b = l.index(max(l))
	if a > b:
		print(a + n - b - 2)
	else:
		print(a + n - b - 1)


for i in range(int(input())):
	Length = int(input())
	li = list(map(int, input().split()))
	maxs = max(li)
	z = li.index(1)
	n = li.index(maxs)
	if z > n:
		print(z + Length - n - 2)
	else:
		print(z + Length - n - 1)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	imin = arr.index(min(arr)) + 1
	imax = arr.index(max(arr)) + 1
	if imin > imax:
		print(n - imax + (imin - 2))
	else:
		print(n - imax + (imin - 1))


T = int(input())
for i in range(T):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = l.index(1) + 1
	ln = l.index(n) + 1
	if l1 < ln:
		total = n - ln + (l1 - 1)
	else:
		total = n - ln + (l1 - 2)
	print(total)


for t in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	first = 0
	last = 0
	for i in range(n):
		if p[i] == 1:
			first = i + 1
			pass
		elif p[i] == n:
			last = i + 1
			pass
		pass
	if first < last:
		print(first - 1 + n - last)
		pass
	else:
		print(first + n - last - 2)
		pass
	pass


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k1 = l.index(1)
	c = 0
	for i in range(k1, 0, -1):
		t = l[i]
		l[i] = l[i - 1]
		l[i - 1] = t
		c += 1
	k2 = l.index(n)
	for i in range(k2, n - 1):
		t = l[i]
		l[i] = l[i + 1]
		l[i + 1] = t
		c += 1
	print(c)


n = int(input())
for i in range(n):
	l = int(input())
	lis = list(map(int, input().split()))
	a = lis.index(1)
	b = lis.index(l)
	if a == 0 and b == l - 1:
		print(0)
	elif a != 0 and b != l - 1:
		print(a + l - b - 1 - int(a > b))
	else:
		print(a + l - b - 1)


t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	for i in range(0, n):
		if s[i] == n:
			ma = i
		elif s[i] == 1:
			mi = i
	swap = n - 1 - ma
	if swap == 0:
		print(swap + mi)
	elif ma > mi:
		print(swap + mi)
	else:
		print(swap + mi - 1)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if l[0] == 1 and l[-1] == n:
		print(0)
	else:
		c = n - l.index(n) - 1
		l.append(max(l))
		l.remove(max(l))
		print(c + l.index(1))


n = int(input())
for i in range(n):
	n = int(input())
	l = list(map(int, input().split()))
	s = 0
	s = l.index(max(l))
	s = n - s - 1
	l.append(max(l))
	l.remove(max(l))
	s2 = l.index(min(l))
	print(s2 + s)


T = int(input())
for t in range(T):
	a = int(input())
	b = list(map(int, input().split()))
	count = 0
	loc_1st = b.index(1)
	loc_last = b.index(a)
	if loc_1st < loc_last:
		print(loc_1st + (a - 1 - loc_last))
	else:
		print(loc_1st + (a - 1 - loc_last - 1))


for _ in range(int(input())):
	x = int(input())
	list1 = list(map(int, input().split()))
	list1 = list(list1)
	lenght = len(list1) - 1
	maxi = max(list1)
	one_index = list1.index(1)
	maxi_index = list1.index(maxi)
	ans = 0
	if one_index > maxi_index:
		ans = one_index + lenght - maxi_index - 1
	else:
		ans = one_index + lenght - maxi_index
	print(ans)


for t in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	c = 0
	if l[0] == 1 and l[n - 1] == n:
		print(0)
	else:
		a = l.index(1)
		b = l.index(n)
		if a < b:
			v = a + (n - 1 - b)
		else:
			v = a + (n - 2 - b)
		print(v)


t = int(input())
for _ in range(t):
	n = int(input())
	p = [int(x) for x in input().split()]
	loc1 = p.index(1)
	locn = p.index(n)
	print(n - 1 - locn + loc1 - int(loc1 > locn))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = l.index(1)
	l2 = l.index(n)
	print(n - 1 - l2 + l1 - int(l1 > l2))


t = int(input())
for i in range(t):
	s = int(input())
	l = list(map(int, input().split()))
	loc1 = l.index(1)
	locs = l.index(s)
	print(s - 1 - locs + loc1 - int(loc1 > locs))


t = int(input())
for i in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	ans = 0
	x = p.index(1)
	y = p.index(n)
	if x == 0 and y == n - 1:
		print(0)
	elif x > y:
		swap1 = n - 1 - y
		swap2 = x
		ans = swap1 + swap2 - 1
		print(ans)
	else:
		swap1 = n - 1 - y
		swap2 = x
		ans = swap1 + swap2
		print(ans)


for _ in range(int(input())):
	x = int(input())
	a = list(map(int, input().split()))
	posN = a.index(x)
	pos1 = a.index(1)
	if pos1 == 0 and posN == x - 1:
		print(0)
	elif pos1 > posN:
		swap1 = x - 1 - posN
		swap2 = pos1
		print(swap1 + swap2 - 1)
	else:
		swap1 = x - 1 - posN
		swap2 = pos1
		print(swap1 + swap2)


for i in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	frst = p.index(1)
	last = p.index(n)
	if frst == 0 and last == n - 1:
		print(0)
	elif frst == 0 and last != n - 1:
		print(n - 1 - last)
	elif last == n - 1 and frst != 0:
		print(frst)
	else:
		c = frst
		l = 0
		for i in range(last, n - 1):
			(p[i], p[i + 1]) = (p[i + 1], p[i])
			l = l + 1
		frst = p.index(1)
		print(l + frst)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if l[0] == 1 and l[n - 1] == n:
		print(0)
	else:
		a = 0
		for i in range(n):
			if l[i] == 1:
				b = i
			if l[i] == n:
				c = i
		if b < c:
			print(b + n - c - 1)
		else:
			print(b + n - c - 2)


T = int(input())
for i in range(T):
	N = int(input())
	P = list(map(int, input().split()))
	l = P.index(1)
	m = P.index(N)
	if m > l:
		print(l + N - 1 - m)
	else:
		print(l + N - m - 2)


ij = int(input())
for kk in range(ij):
	n = int(input())
	p = list(map(int, input().split()))
	l1 = p.index(1)
	l2 = p.index(n)
	print(n - 1 - l2 + l1 - int(l1 > l2))


n = int(input())
for _ in range(n):
	x = int(input())
	l = list(map(int, input().split()))
	m = max(l)
	a = min(l)
	count = 0
	for i in range(x):
		if l[i] == m:
			i_ = i
		if l[i] == a:
			j = i
	if i_ > j:
		print(j + x - i_ - 1)
	if i_ < j:
		print(j + x - i_ - 2)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(a, b) = (arr.index(1), arr.index(n))
	if b < a:
		print(a + (n - b - 1) - 1)
	else:
		print(a + (n - b - 1))


t = int(input())
for i in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	m1 = p.index(1)
	mn = p.index(n)
	print(n - 1 - mn + m1 - int(m1 > mn))


t = int(input())
for i in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	l1 = p.index(1)
	l2 = p.index(n)
	print(n - 1 - l2 + l1 - int(l1 > l2))


T = int(input())
for i in range(T):
	N = int(input())
	P = list(map(int, input().split()))
	count = 0
	if P[0] == 1 and P[N - 1] == N:
		print(0)
	else:
		index_1 = P.index(1)
		index_N = N - 1 - P.index(N)
		if P.index(1) > P.index(N):
			count = index_1 + index_N - 1
		else:
			count = index_1 + index_N
		print(count)


def endsort(x):
	i_1 = x.index(1)
	i_n = x.index(len(x))
	if i_1 < i_n:
		return i_1 - i_n + len(x) - 1
	else:
		return i_1 - i_n + len(x) - 2
a = int(input())
l = []
for _ in range(a):
	l.append(input())
	l.append([int(x) for x in input().split()])
for i in range(len(l)):
	if i % 2 != 0:
		print(endsort(l[i]))


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	a = p.index(1)
	b = p.index(n)
	print(n - 1 - b + a - int(a > b))


t = int(input())
for _ in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	l1 = p.index(1)
	ln = p.index(n)
	print(n - 1 - ln + l1 - int(l1 > ln))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	(i1, i2) = (0, 0)
	for j in range(len(a)):
		if a[j] == 1:
			i1 = j
		if a[j] == len(a):
			i2 = j
	if i1 < i2:
		nop = i1 + len(a) - i2 - 1
	else:
		nop = i1 + len(a) - i2 - 2
	print(nop)


for T in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	id_1 = -1
	id_n = -1
	for i in range(n):
		if p[i] == 1:
			id_1 = i
		elif p[i] == n:
			id_n = i
	D1 = id_1
	Dn = n - 1 - id_n
	if id_1 < id_n:
		print(D1 + Dn)
	else:
		print(D1 + Dn - 1)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	i1 = l.index(1)
	i2 = l.index(n)
	if i1 < i2:
		print(i1 + (n - 1 - i2))
	else:
		print(i1 + (n - 1 - i2 - 1))


for _ in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	l1 = li.index(1)
	ln = li.index(n)
	print(n - 1 - ln + l1 - int(l1 > ln))


t = int(input())
for _ in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	f = p.index(1)
	l = p.index(n)
	print(n - 1 - l + f - int(f > l))


for i in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	if p[0] == 1 and p[n - 1] == n:
		print(0)
		continue
	ans = 0
	k = n - 1
	j = 0
	if p[0] != 1:
		j = p.index(1)
		ans += j
	if p[n - 1] != n:
		k = p.index(n)
		ans += n - 1 - k
	if k < j:
		ans -= 1
	print(ans)


n = int(input())
while n:
	t = int(input())
	l = list(map(int, input().split()))
	if l[0] == 1 and l[t - 1] == t:
		print('0')
	elif l[0] == 1:
		print(t - l.index(t) - 1)
	elif l[t - 1] == t:
		print(l.index(1))
	else:
		a = l.index(t)
		b = l.index(1)
		if a < b:
			print(t - l.index(t) - 2 + l.index(1))
		else:
			print(t - l.index(t) - 1 + l.index(1))
	n -= 1


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = l.index(1)
	ln = l.index(n)
	if ln > l1:
		print(n - 1 - ln + l1)
	else:
		print(n - 1 - ln + l1 - 1)


for i in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	if x[0] == 1 and x[-1] == n:
		print(0)
	elif x.index(1) > x.index(n):
		print(x.index(1) + (n - 1 - x.index(n) - 1))
	else:
		print(x.index(1) + n - 1 - x.index(n))


for z in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	loc1 = l.index(1)
	locn = l.index(n)
	print(n - 1 - locn + loc1 - int(loc1 > locn))