\textit {Life is change, change is stability.} 

Chef calls a sequence of integers A_{1}, A_{2}, \ldots, A_{N} stable if all the elements in the sequence are equal.

Chef gives you a sequence A_{1}, A_{2}, \ldots, A_{N}. You may perform the following operations on the sequence any number of times (possibly 0):
1. Select any prefix A[1 \ldots k] such that max(A[1 \ldots k]) = A[k] and set A[i] := A[k] \forall i \in [1,k-1]. For example, if the sequence  A = [\textcolor{blue}{3,1,4},5,9] , then choosing k = 3 yields the sequence  [\textcolor{blue}{4,4,4},5,9] .

2. Select any segment A[L \ldots R] and shift the segment cyclically to the left keeping other elements unchanged. For example, if the sequence  A = [3, \textcolor{blue}{4,1,5} ,9] , then choosing L = 2 and R = 4 yields the sequence [3, \textcolor{blue}{1,5,4} ,9].

Chef is asking you to find the minimum number of operations required to make the sequence stable.

It is guaranteed that you can always make the sequence stable using such operations.

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

- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}.

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

For each test case, print the minimum number of operations required to make the sequence stable.

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

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 100$
$1 ≤ A_{i} ≤ 100$ for each valid $i$

----- Sample Input 1 ------ 
2
3
1 1 1
2
69 96
----- Sample Output 1 ------ 
0
1
----- explanation 1 ------ 
Test Case $1$: The sequence is already stable, so we require $0$ operations.

Test Case $2$: We can apply operation $1$ on the prefix $A[1 \dots 2]$ which converts $A$ into $ [96,96] $ which is stable.

Difficulty: MEDIUM
Tags: Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
T = int(input())
for _ in range(T):
	o = int(input())
	l = list(map(int, input().split()))
	n = max(l)
	a = l.copy()
	l.sort()
	if l[0] == n:
		print(0)
	elif a[-1] == n:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	q = max(a)
	if a == [q] * n:
		print(0)
	elif a[-1] == q:
		print(1)
	else:
		print(2)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if a.count(a[0]) == n:
		print('0')
	else:
		b = max(a)
		if a[-1] == b:
			print('1')
		else:
			print('2')


t = int(input())
for test_case in range(0, t):
	n = int(input())
	array = list(map(int, input().split()))
	if len(set(array)) == 1:
		print(0)
	elif max(array) == array[-1]:
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = 0
	mindex = 0
	for i in range(n - 1, -1, -1):
		if a[i] > m:
			m = a[i]
			mindex = i
	k = n - 1 - mindex
	c = 0
	if k % 2 == 0:
		c = k // 2
	else:
		c = k // 2 + 1
	if min(a) == m:
		print(0)
	elif mindex == n - 1:
		print(1)
	else:
		print(2)


t = int(input())
while t > 0:
	n = int(input())
	a = [int(i) for i in input().split()]
	maxi = 0
	for i in a:
		maxi = max(maxi, i)
	isequal = 1
	for i in a:
		if i != maxi:
			isequal = 0
	if isequal:
		print(0)
	elif a[n - 1] == maxi:
		print(1)
	else:
		print(2)
	t = t - 1


def stable(a):
	for i in a:
		if i != a[0]:
			return False
	return True

def max_count(a, max_ind):
	m_num = max(a)
	if a[-1] == m_num:
		return 1
	return 2
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	max_ind = a.index(max(a))
	if stable(a) == True:
		print(0)
	else:
		print(max_count(a, max_ind))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if len(set(l)) == 1:
		print(0)
	elif l[n - 1] == max(l):
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if len(set(arr)) == 1:
		print(0)
	elif arr[n - 1] == max(arr):
		print(1)
	else:
		print(2)


tests = int(input())
for i in range(tests):
	length = int(input())
	arr = list(map(int, input().split()))
	maximum = max(arr)
	minimum = min(arr)
	ans = 0
	if minimum != maximum:
		if arr[-1] == maximum:
			ans = 1
		else:
			ans = 2
	print(ans)


from array import *
for _ in range(int(input())):
	n = int(input())
	a = array('i', [int(i) for i in input().split()])
	if len(set(a)) == 1:
		print(0)
	elif a[-1] == max(a):
		print(1)
	else:
		print(2)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	t = 1
	for i in range(n - 1):
		if a[i] != a[i + 1]:
			t = 0
			break
	if t == 1:
		print(0)
	else:
		m = max(a)
		if a[-1] == m:
			print(1)
		else:
			print(2)


for i in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	max1 = list1[0]
	if len(set(list1)) == 1:
		print(0)
	else:
		for j in list1:
			if j > max1:
				max1 = j
		if list1[n - 1] != max1:
			print(2)
		else:
			print(1)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = max(a)
	if len(set(a)) == 1:
		print('0')
		continue
	num = 0
	for i in range(len(a)):
		if a[i] == m:
			num = i
	if num != len(a) - 1:
		print('2')
	else:
		print('1')


a = int(input())
for i in range(a):
	le = int(input())
	arr = list(map(int, input().split()))
	ma = max(arr)
	if len(set(arr)) == 1:
		print(0)
		continue
	for j in range(len(arr)):
		if arr[j] == ma:
			ind = j
	if ind != len(arr) - 1:
		print(2)
	else:
		print(1)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	maxx = 0
	ind = 0
	d = {}
	for i in range(n):
		if a[i] >= maxx:
			maxx = a[i]
			ind = i
		if a[i] not in d:
			d[a[i]] = 1
	if len(d) == 1:
		print(0)
	elif ind == n - 1:
		print(1)
	else:
		print(2)


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	maxi = max(arr)
	if arr.count(maxi) == n:
		print('0')
	elif max(arr) == arr[n - 1]:
		print('1')
	else:
		print('2')
	t -= 1


t = int(input())

def solve():
	N = int(input())
	A = [int(x) for x in input().split(' ')]
	if len(set(A)) == 1:
		print(0)
		return
	maxA = max(A)
	if A[-1] == maxA:
		print(1)
		return
	print(2)
while t:
	solve()
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	low = min(l)
	high = max(l)
	if low == high:
		print('0')
	elif l[-1] == high:
		print('1')
	else:
		print('2')


def solve(n, arr):
	if len(set(arr)) == 1:
		return 0
	mx = max(arr)
	if arr[-1] == mx:
		return 1
	return 2
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(n, arr))


t = int(input())
for i in range(t):
	n = int(input())
	numbers = list(map(int, input().split()))
	count = 1
	for j in range(len(numbers) - 1):
		if numbers[j] == numbers[j + 1]:
			count += 1
		else:
			break
	if count == len(numbers):
		print(0)
	else:
		ordered_numbers = sorted(numbers)
		if ordered_numbers[n - 1] == numbers[n - 1]:
			print(1)
		else:
			print(2)


k = int(input())
for i in range(k):
	m = int(input())
	l = list(map(int, input().split()))
	low = min(l)
	high = max(l)
	if low == high:
		print(0)
	elif l[-1] == high:
		print(1)
	else:
		print(2)


tests = int(input())
for t in range(tests):
	n = int(input())
	a = list(map(int, input().split()))
	if a.count(a[0]) == len(a):
		print(0)
	elif a[-1] == max(a):
		print(1)
	else:
		print(2)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	mini = min(arr)
	maxa = max(arr)
	sol = 0
	if mini == maxa:
		pass
	elif arr[-1] == maxa:
		sol = 1
	else:
		sol = 2
	print(sol)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if all(list(map(lambda x: x == a[0], a))):
		print(0)
	else:
		o = a.index(max(a))
		if a[-1] == max(a):
			print(1)
		else:
			print(2)


tsc = int(input())
for j in range(tsc):
	l = int(input())
	string = input()
	nstring = string.split()
	List = []
	for word in nstring:
		List.append(int(word))
	if List.count(List[0]) == len(List):
		print(0)
	elif max(List) == List[len(List) - 1]:
		print(1)
	else:
		print(2)


t = int(input())
for j in range(t):
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	mini = min(arr)
	maxi = max(arr)
	if mini == maxi:
		print(0)
	elif arr[-1] == maxi:
		print(1)
	else:
		print(2)


import collections
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	con = dict(collections.Counter(l))
	if len(con.keys()) == 1:
		print(0)
	elif max(l) == l[-1]:
		print(1)
	else:
		print(2)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	x = min(a)
	y = max(a)
	s = 0
	if x == y:
		pass
	elif a[-1] == y:
		s = 1
	else:
		s = 2
	print(s)


t = int(input())
for j in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	mi = min(a)
	ma = max(a)
	s = 0
	if mi == ma:
		pass
	elif a[-1] == ma:
		s = 1
	else:
		s = 2
	print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if arr.count(max(arr)) != n and arr[n - 1] != max(arr):
		print(2)
	elif arr.count(max(arr)) != n and arr[n - 1] == max(arr):
		print(1)
	else:
		print(0)


number_of_tests = int(input())
results = []
for _ in range(number_of_tests):
	number_of_operations = 0
	length = int(input())
	nums = tuple(map(int, input().split()))
	maxs = []
	num = nums[0]
	for element in nums:
		if element != num:
			maximum = max(nums)
			if nums[-1] == maximum:
				number_of_operations = 1
			else:
				number_of_operations = 2
			continue
	results.append(number_of_operations)
for result in results:
	print(result)


s = []
for i in range(int(input())):
	input()
	m = list(map(int, input().split()))
	if m.count(max(m)) == len(m):
		s.append(0)
	elif m[-1] == max(m):
		s.append(1)
	else:
		s.append(2)
for i in s:
	print(i)


T = int(input())
for t in range(0, T):
	N = int(input())
	arr = list(map(int, input().split(' ')))
	ind = arr.index(max(arr))
	flag = 0
	if len(set(arr)) == 1:
		flag = 1
	if arr[N - 1] == max(arr) and flag == 0:
		print(1)
	elif flag == 1:
		print(0)
	else:
		print(2)


t = int(input())
for tc in range(0, t):
	n = int(input())
	arr = list(map(int, input().split()))
	l = len(arr)
	flg = 0
	for i in range(l):
		if arr[i] != arr[0]:
			flg = 1
			break
	if flg == 0:
		print(0)
	else:
		m = max(arr)
		for i in range(l):
			if m == arr[i]:
				ind = i
		if ind == l - 1:
			print(1)
		else:
			print(2)


import math

def main():
	t = int(input())
	while t > 0:
		n = int(input())
		A = [int(x) for x in input().split()]
		flag = True
		ans = 2
		maxm = A[0]
		for i in range(1, len(A)):
			if A[i] != A[i - 1]:
				flag = False
			maxm = max(maxm, A[i])
		if flag:
			ans = 0
		elif maxm == A[len(A) - 1]:
			ans = 1
		print(ans)
		t -= 1
main()


s = int(input())
for _ in range(s):
	n = int(input())
	a = [int(i) for i in input().split()]
	mini = min(a)
	maxa = max(a)
	if mini == maxa:
		sol = 0
	elif a[-1] == maxa:
		sol = 1
	else:
		sol = 2
	print(sol)


T = int(input())
for t in range(T):
	N = int(input())
	List = list(map(int, input().strip().split()))[:N]
	if all((element == List[0] for element in List)):
		print(0)
	elif max(List) == List[N - 1]:
		print(1)
	else:
		print(2)


t = int(input(''))
for i in range(0, t):
	b = int(input())
	l = list(map(int, input('').split()))
	a = max(l)
	if len(set(l)) == 1:
		print('0')
	elif l[len(l) - 1] == a:
		print('1')
	else:
		print('2')


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if n == l.count(l[0]):
		c = 0
	elif l[-1] == max(l):
		c = 1
	else:
		c = 2
	print(c)


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	if lst.count(lst[0]) == len(lst):
		count = 0
	elif lst[-1] == max(lst):
		count = 1
	else:
		count = 2
	print(count)


for _ in range(int(input())):
	N = int(input())
	a = list(map(int, input().split()))
	(mini, maxi) = (min(a), max(a))
	s = 0
	if mini == maxi:
		s = 0
	elif a[-1] == maxi:
		s = 1
	else:
		s = 2
	print(s)


t = int(input())
for test in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	if len(set(arr)) == 1:
		print(0)
	elif max(arr) == arr[-1]:
		print(1)
	else:
		print(2)


q = int(input())
for _ in range(q):
	n = int(input())
	t = list(map(int, input().split()))
	w = t[0]
	x = True
	for i in range(n):
		if t[i] != w:
			x = False
	if x:
		print(0)
	elif max(t) == t[n - 1]:
		print(1)
	else:
		print(2)


for i in range(int(input())):
	lenr = int(input())
	rry = list(map(int, input().split()))
	ele = rry[0]
	lstele = rry[-1]
	if rry.count(ele) == lenr:
		print(0)
	elif max(rry) == lstele:
		print(1)
	else:
		print(2)


cs = int(input())
for i in range(cs):
	n = int(input())
	lst = [int(i) for i in input().split(' ')]
	st = set(lst)
	if len(st) == 1:
		print('0')
	elif max(lst) == lst[-1]:
		print('1')
	else:
		print('2')


try:
	t = int(input())
	while t > 0:
		n = int(input())
		a = [int(i) for i in input().split()]
		maxi = 0
		for i in a:
			maxi = max(maxi, i)
		isEqual = 1
		for i in a:
			if i != maxi:
				isEqual = 0
		if isEqual:
			print(0)
		elif a[n - 1] == maxi:
			print(1)
		else:
			print(2)
	t = t - 1
except:
	pass


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	mn = min(arr)
	mx = max(arr)
	if mn == mx:
		print(0)
	elif arr[-1] == mx:
		print(1)
	else:
		print(2)


k = int(input())
for i in range(k):
	n = int(input())
	t = list(map(int, input().split()))
	m = min(t)
	s = max(t)
	r = 0
	if m == s:
		pass
	elif t[-1] == s:
		r = 1
	else:
		r = 2
	print(r)


t = int(input())
for x in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	if min(l) == max(l):
		pass
	elif max(l) == l[-1]:
		c = 1
	else:
		c = 2
	print(c)


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	a = [int(i) for i in sys.stdin.readline().split()][:n]
	if len(set(a)) != 1:
		if a[-1] == max(a):
			print(1)
		else:
			print(2)
	else:
		print(0)


t = int(input())
for i in range(t):
	maxx = ''
	flag = ''
	n = int(input())
	l = list(map(int, input().split()))
	for i in range(len(l) - 1):
		if l[i] == l[i + 1]:
			continue
		else:
			flag = 'not equal'
			break
	if flag == 'not equal':
		maxx = max(l)
		if l[len(l) - 1] == maxx:
			print(1)
			continue
		if l[len(l) - 1] != maxx:
			print(2)
			continue
	if flag == '':
		print(0)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr_max = arr[0]
	for i in range(1, n):
		arr_max = max(arr_max, arr[i])
	flag = True
	for j in range(n):
		if arr[j] != arr_max:
			flag = False
			break
	if flag:
		print(0)
	elif arr[n - 1] == arr_max:
		print(1)
	else:
		print(2)


for x in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	if A.count(A[0]) == len(A):
		print(0)
	elif max(A) != A[N - 1]:
		print(2)
	else:
		print(1)


t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	maxi = 0
	for i in a:
		maxi = max(maxi, i)
	isEqual = 1
	for i in a:
		if i != maxi:
			isEqual = 0
	if isEqual:
		print('0\n')
	elif a[n - 1] == maxi:
		print('1\n')
	else:
		print('2\n')


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


T = int(input())
for t in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	maxi = 0
	j = 0
	z = 0
	for i in range(n):
		if a[i] >= maxi:
			j = i
			maxi = a[i]
		if a[i] != a[0]:
			z = 1
	if z == 1:
		if j != n - 1:
			print(2)
		else:
			print(1)
	else:
		print(0)


import sys
import math

def findMax(arr, n):
	maxi = arr[0]
	for i in range(1, n):
		if arr[i] >= maxi:
			maxi = arr[i]
	if arr[n - 1] == maxi:
		return True
	else:
		return False

def isValid(arr, n):
	x = arr[0]
	for i in range(1, n):
		if arr[i] != x:
			return False
	return True

def main():
	test_case = int(sys.stdin.readline())
	for tc in range(test_case):
		n = int(sys.stdin.readline())
		arr = [int(a) for a in sys.stdin.readline().split()]
		if isValid(arr, n):
			print(0)
		elif findMax(arr, n):
			print(1)
		else:
			print(2)
main()


for i in range(int(input())):
	k = int(input())
	n = list(map(int, input().split()[:k]))
	c = 0
	for i in range(len(n) - 1):
		if n[i] == n[i + 1]:
			c += 1
	if c == len(n) - 1:
		print(0)
	elif n[-1] == max(n):
		print(1)
	else:
		print(2)


out = []
T = int(input())
for t in range(T):
	N = int(input())
	nums = list(map(int, input().split()))
	is_stable = 1
	for n in nums:
		if n != nums[0]:
			is_stable = 0
			break
	if is_stable:
		out.append(0)
	else:
		max_num = max(nums)
		if nums[-1] == max_num:
			out.append(1)
		else:
			out.append(2)
for o in out:
	print(o)


for _ in range(int(input())):
	n = int(input())
	lis = [*map(int, input().split())]
	if all((i == lis[0] for i in lis)):
		print(0)
	elif max(lis) == lis[-1]:
		print(1)
	else:
		print(2)


def func(N, arr):
	i = 0
	if len(set(arr)) == 1:
		return 0
	if arr[-1] == max(arr):
		return 1
	return 2
T = int(input())
for i in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	print(func(N, arr))


for _ in range(int(input())):
	length = int(input())
	lt = [int(x) for x in input().split(' ')]
	for i in range(length):
		if i == 0:
			maximum = lt[i]
			(rep_count, ind) = (0, 0)
		if maximum == lt[i]:
			rep_count += 1
		if maximum <= lt[i]:
			maximum = lt[i]
			ind = i
	if rep_count == length:
		print('0')
	elif ind == length - 1:
		print('1')
	elif ind < length - 1:
		print('2')