Given an array A of size N. 

You can do the following operation on the array:
Pick any 2 distinct indices i and j such that A_{i}=A_{j};
Change all the elements between the indices i and j to A_{i}, i.e, for all k (i ≤ k ≤ j), set A_{k}=A_{i}.

Find the minimum number of operations required to sort the array in non-decreasing order. If it is not possible to sort the array, print -1 instead.

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

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N - the size of the array A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

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

For each test case, the minimum number of operations required to sort the array. If it is not possible to sort the array, print -1 instead.

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$0 ≤ A_{i} ≤ N $
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
6
1 2 1 3 4 3
3
3 1 2
----- Sample Output 1 ------ 
2
-1
----- explanation 1 ------ 
Test Case $1$: We can sort the array using $2$ operations. 
- In the first operation select indices $1$ and $3$. After this operation, the array will be $A = [1,1,1,3,4,3]$.
- In the second operation select indices $4$ and $6$. After this operation, the array will be $A = [1,1,1,3,3,3]$.

Thus, the array is sorted using $2$ operations. It can be proven that the array cannot be sorted in less than $2$ operations.

Test Case $2$: It is not possible to sort the array using any number of operations.

Difficulty: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
for _ in range(int(input())):
	N = int(input())
	A = [*map(int, input().split())]
	(op, dp) = ([pow(10, 9)] * (N + 1), [pow(10, 9)] * (N + 1))
	op[A[0]] = dp[0] = 0
	for i in range(1, N):
		if A[i - 1] <= A[i]:
			dp[i] = dp[i - 1]
		dp[i] = min(dp[i], op[A[i]] + 1)
		op[A[i]] = min(op[A[i]], dp[i])
	print(dp[N - 1] if dp[N - 1] <= N else -1)


import collections
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	dp = [int(1000000000.0)] * (n + 1)
	prev = collections.defaultdict(lambda : int(1000000000.0))
	dp[0] = prev[arr[0]] = 0
	for i in range(1, n):
		if arr[i - 1] <= arr[i]:
			dp[i] = dp[i - 1]
		minn = prev[arr[i]]
		dp[i] = min(dp[i], minn + 1)
		prev[arr[i]] = min(minn, dp[i])
	print(dp[n - 1] if dp[n - 1] <= n - 1 else -1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(last, ans) = ([-1 for _ in range(n + 1)], [float('inf') for _ in range(n)])
	(last[l[0]], ans[0]) = (0, 0)
	for i in range(1, n):
		if last[l[i]] != -1:
			if ans[i - 1] == float('inf') or l[i] - l[i - 1] < 0:
				ans[i] = ans[last[l[i]]] + 1
			else:
				ans[i] = min(ans[i - 1], ans[last[l[i]]] + 1)
		elif l[i] - l[i - 1] >= 0 and ans[i - 1] != float('inf'):
			(ans[i], last[l[i]]) = (ans[i - 1], i)
	if ans[-1] == float('inf'):
		ans[-1] = -1
	print(ans[-1])


import sys
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	dp = [sys.maxsize] * n
	val = [sys.maxsize] * (max(arr) + 1)
	dp[0] = 0
	val[arr[0]] = 0
	for i in range(1, n):
		if arr[i] >= arr[i - 1]:
			dp[i] = dp[i - 1]
		dp[i] = min(dp[i], val[arr[i]] + 1)
		val[arr[i]] = min(dp[i], val[arr[i]])
	if dp[-1] > 10 ** 6:
		print(-1)
	else:
		print(dp[-1])


from collections import defaultdict
maxx = 10000000.0
for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	dp = [0]
	mp = defaultdict(lambda : maxx)
	mp[nums[0]] = 0
	for i in range(1, n):
		dp.append(min(mp[nums[i]] + 1, maxx))
		if nums[i] >= nums[i - 1]:
			dp[i] = min(dp[i], dp[i - 1])
			mp[nums[i]] = min(mp[nums[i]], dp[i])
	print(-1 if dp[n - 1] == maxx else dp[n - 1])


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	a.insert(0, 0)
	dp = [0] * 200001
	q = [0] * 200001
	for i in range(2, n + 1):
		dp[i] = float('inf')
	for i in range(n + 1):
		q[i] = float('inf')
	for i in range(1, n + 1):
		dp[i] = min(dp[i], q[a[i]] + 1)
		if a[i] >= a[i - 1]:
			dp[i] = min(dp[i], dp[i - 1])
		if a[i - 1] <= a[i]:
			q[a[i]] = min(q[a[i]], dp[i])
	if dp[n] == float('inf'):
		print(-1)
	else:
		print(dp[n])
	t = t - 1


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dp = [float('inf')] * n
	v = [float('inf')] * (n + 1)
	dp[0] = 0
	v[a[0]] = 0
	for i in range(1, n):
		if a[i - 1] <= a[i]:
			dp[i] = dp[i - 1]
		dp[i] = min(dp[i], 1 + v[a[i]])
		v[a[i]] = min(v[a[i]], dp[i])
	if dp[n - 1] == float('inf'):
		print(-1)
	else:
		print(dp[n - 1])


INF = 10 ** 9
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	min_idx = {}
	for i in range(n):
		if a[i] not in min_idx:
			min_idx[a[i]] = INF
	dp = [INF] * n
	dp[0] = 0
	min_idx[a[0]] = 0
	for i in range(1, n):
		if a[i] >= a[i - 1]:
			dp[i] = dp[i - 1]
		m = min_idx[a[i]]
		dp[i] = min(dp[i], 1 + m)
		min_idx[a[i]] = min(min_idx[a[i]], dp[i])
	if dp[n - 1] >= INF:
		print(-1)
	else:
		print(dp[n - 1])


maxx = 2147483647
for _ in range(int(input())):
	n = int(input())
	nums = [0] + list(map(int, input().split()))
	dp = [0, 0] + [maxx] * (n - 1)
	q = [maxx] * (n + 1)
	for i in range(1, n + 1):
		dp[i] = min(dp[i], q[nums[i]] + 1)
		if nums[i] >= nums[i - 1]:
			dp[i] = min(dp[i], dp[i - 1])
		if nums[i - 1] <= nums[i]:
			q[nums[i]] = min(q[nums[i]], dp[i])
	print(-1 if dp[n] == maxx else dp[n])


dp = [0] * (int(200000.0) + 1)
q = [0] * (int(200000.0) + 1)

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

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

def fact(n):
	if n == 1:
		return 1
	return n * fact(n - 1)

def cbits(n):
	count = 0
	while n:
		n = n & n - 1
		count += 1
	return count

def solve(n, arr):
	for i in range(2, n + 1):
		dp[i] = int(20000000000.0)
	for i in range(n + 1):
		q[i] = int(20000000000.0)
	for i in range(1, n + 1):
		dp[i] = min(dp[i], q[arr[i]] + 1)
		if arr[i] >= arr[i - 1]:
			dp[i] = min(dp[i], dp[i - 1])
		if arr[i - 1] <= arr[i]:
			q[arr[i]] = min(q[arr[i]], dp[i])
	if dp[n] == int(20000000000.0):
		print(-1)
	else:
		print(dp[n])
t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	arr = [0] + arr
	solve(n, arr)
	t -= 1


import sys, math, heapq, bisect
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
ints = lambda : list(map(int, input().split()))
p = 10 ** 9 + 7
inf = 10 ** 20 + 7
for t in range(int(input())):
	n = int(input())
	a = ints()
	b = [a[0]]
	for i in a[1:]:
		if i != b[-1]:
			b.append(i)
	a = list(b)
	a = a[::-1]
	n = len(a)
	dp = {}
	dp[a[0]] = 0
	prev = 0
	for i in range(1, n):
		if a[i] > a[i - 1]:
			if a[i] in dp:
				prev = dp[a[i]] + 1
			else:
				prev = -1
		elif prev == -1:
			if a[i] in dp:
				prev = dp[a[i]] + 1
		else:
			dp[a[i]] = prev
	ans = prev
	a = a[::-1]
	dp = {}
	dp[a[0]] = 0
	prev = 0
	for i in range(1, n):
		if a[i] < a[i - 1]:
			if a[i] in dp:
				prev = dp[a[i]] + 1
			else:
				prev = -1
		elif prev == -1:
			if a[i] in dp:
				prev = dp[a[i]] + 1
		else:
			dp[a[i]] = prev
	prev = min(prev, ans)
	print(prev)


from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(5 * 10 ** 5)
inp = lambda : list(map(int, input().split()))

def solve(i, j):
	if i == n:
		return 0
	if i - 1 >= 0 and j == 0 and (a[i - 1] > a[i]):
		return float('inf')
	if dp[i][j] != -1:
		return dp[i][j]
	ans = solve(i + 1, 0)
	if nind[i] != n:
		if j == 1:
			ans = min(ans, solve(nind[i], 1))
		else:
			ans = min(ans, solve(nind[i], 1) + 1)
	dp[i][j] = ans
	return ans

def answer():
	global dp, nind
	best = [n for i in range(n + 1)]
	nind = [n for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		nind[i] = best[a[i]]
		best[a[i]] = i
	dp = [[-1, -1] for i in range(n)]
	ans = solve(0, 0)
	if ans == float('inf'):
		return -1
	return ans
for T in range(int(input())):
	n = int(input())
	a = inp()
	print(answer())