Read problem statements in [Mandarin], [Bengali], [Russian], and [Vietnamese] as well.

Chef is very adventurous, so he asked Bob to give him a task.

Bob gave him a sequence of blocks with heights A_{1}, A_{2}, \ldots, A_{N}. Chef is at the first block and he has to reach the N-th block using the minimum number of moves to complete the task.

In one move, he can jump from the i-th block to the j-th block only if the following conditions are satisfied:
i < j
A_{i} ≥ A_{j}
for all k (i < k < j), A_{k} ≤ A_{j}

You have to find the minimum number of moves Chef needs to perform to reach the last block, or determine that it is impossible.

------ 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 contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}.

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

For each test case, print a single line containing one integer --- the minimum number of moves or -1 if it is impossible to reach the last block.

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

$1 ≤ T ≤ 100$
$2 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} ≤ 10^{5}$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $10^{6}$

------ subtasks ------ 

Subtask #1 (30 points):
$2 ≤ N ≤ 1,000$
the sum of $N$ over all test cases does not exceed $5 \cdot 10^{4}$

Subtask #2 (70 points): original constraints

----- Sample Input 1 ------ 
2
5
9 15 8 13 8
9
20 16 13 9 17 11 15 8 7
----- Sample Output 1 ------ 
-1
4
----- explanation 1 ------ 
Example case 1: There is no way to move from the first block (with height $9$) to any other block.

Example case 2: The only sequence of $4$ moves is $20 \rightarrow 17 \rightarrow 15 \rightarrow 8 \rightarrow 7$. For example, in the first move, all the heights between $20$ and $17$ do not exceed $17$, so all conditions are satisfied.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
t = int(input())
for i in range(t):
	N = int(input())
	L = list(map(int, input().split()))
	if L[0] < max(L):
		print(-1)
		continue
	stack = []
	for i in range(1, N):
		if len(stack) == 0 or L[i] < stack[-1]:
			stack.append(L[i])
		else:
			while len(stack) > 0 and stack[-1] <= L[i]:
				stack.pop()
			stack.append(L[i])
	print(len(stack))


try:
	t = int(input())
	for i in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		m = -1
		count = 0
		if a[0] == max(a):
			for j in range(n - 1, 0, -1):
				if a[j] > m:
					m = a[j]
					count = count + 1
			print(count)
		else:
			print(-1)
except:
	pass


import sys
from collections import Counter, deque
from math import gcd, sqrt, ceil

def li():
	return [int(i) for i in sys.stdin.readline().split()]

def si():
	return sys.stdin.readline().split()

def ii():
	return int(sys.stdin.readline())

def ip():
	return sys.stdin.readline()[:-1]
for tastcas in range(int(input())):
	n = ii()
	a = li()
	m = -1
	c = 0
	if a[0] == max(a):
		for j in range(n - 1, 0, -1):
			if a[j] > m:
				m = a[j]
				c = c + 1
		print(c)
	else:
		print(-1)


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


t = int(float(input()))
for _ in range(t):
	n = int(float(input()))
	a = list(map(int, input().split()))
	st = []
	flag = 0
	for i in range(1, n):
		if a[i] > a[0]:
			print('-1')
			flag = 1
			break
	if flag == 0:
		curr_max = -1
		for i in range(n - 1, 0, -1):
			if a[i] > curr_max:
				curr_max = a[i]
				st.append(curr_max)
		print(len(st))


try:
	for t in range(int(input())):
		N = int(input())
		A = list(map(int, input().split()))
		i = 0
		count = 0
		flag = 0
		max_arr = [A[-1]]
		curr = N - 1
		max_index = [N - 1]
		for i in range(N - 2, -1, -1):
			if A[i] > max_arr[-1]:
				max_arr.append(A[i])
				curr = i
				max_index.append(curr)
			else:
				max_arr.append(max_arr[-1])
				max_index.append(curr)
		max_arr.reverse()
		max_index.reverse()
		while i < N - 1:
			if max_arr[i + 1] <= A[i]:
				i = max_index[i + 1]
				count += 1
			else:
				print(-1)
				flag = 1
				break
		if flag == 1:
			continue
		print(count)
except:
	pass


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	if l[0] != max(l):
		print(-1)
		continue
	if len(set(l)) == 1:
		print(1)
		continue
	j = n - 2
	s = sorted(list(set(l)))[-2]
	mx = l[n - 1]
	while j >= 0:
		if l[j] > mx:
			ans += 1
		mx = max(l[j], mx)
		j -= 1
	if l.count(mx) > 1:
		ans += 1
	print(ans)


for _ in range(int(input())):
	a = int(input())
	l = [int(i) for i in input().split()]
	right = []
	stack = []
	for i in range(a - 1, -1, -1):
		while stack != [] and stack[-1] < l[i]:
			stack.pop()
		if i == a - 1 or i == 0:
			right.append(l[i])
		elif stack == []:
			right.append(l[i])
		else:
			right.append(-1)
		stack.append(l[i])
	res1 = []
	for i in right[::-1]:
		if i != -1:
			res1.append(i)
	count = 0
	valid = True
	for i in range(0, len(res1) - 1):
		if res1[i] >= res1[i + 1]:
			count += 1
		else:
			valid = False
			break
	if valid == False:
		print(-1)
	else:
		print(count)


for _ in range(int(input())):
	n = int(input())
	blocks = list(map(int, input().split()))
	j = 1
	mx = blocks[n - 1]
	for i in range(n - 1, 1, -1):
		if blocks[i - 1] > mx:
			j += 1
			mx = blocks[i - 1]
	if blocks[0] >= mx:
		print(j)
	else:
		print(-1)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	ans = 0
	m = -1
	for i in range(N - 1, 0, -1):
		if A[i] > m:
			ans += 1
			m = A[i]
	if m <= A[0]:
		print(ans)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = a[::-1]
	(maxh, ans) = (a[0], 0)
	for i in range(n - 1):
		if maxh < a[i]:
			ans += 1
			maxh = a[i]
	if a[n - 1] >= maxh:
		print(ans + 1)
	else:
		print(-1)


import bisect as bs
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	vis = [0] * n
	s = sorted(l)
	d = {}
	last = {}
	for i in range(n - 1, -1, -1):
		if s[i] not in d:
			d[s[i]] = []
		d[s[i]].append(i)
	for i in range(n):
		last[l[i]] = i
	j = n - 1
	ans = 0
	if l[0] != s[-1]:
		print(-1)
		continue
	else:
		i = 1
		vis[n - 1] = 1
		while i < n:
			while j >= 0 and vis[j] == 1:
				j -= 1
			ans += 1
			x = last[s[j]]
			while i < n and i != x:
				vis[d[l[i]].pop()] = 1
				i += 1
			if i == n:
				break
			else:
				vis[d[l[i]].pop()] = 1
			i += 1
		print(ans)


t = int(input())
for j in range(t):
	n = int(input())
	a = [int(i) for i in input().split()][:n]
	q = 0
	c = 0
	a.reverse()
	for i in range(n):
		if i != n - 1:
			if a[q] < a[i + 1]:
				c += 1
				q = i + 1
			elif a[q] == a[i + 1] and i + 1 != n - 1:
				q = i + 1
			elif a[q] == a[i + 1] and i + 1 == n - 1:
				c += 1
				q = i + 1
	if q == n - 1:
		print(c)
	else:
		print('-1')


for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	lmax = h[n - 1]
	res = 0
	for i in range(n - 2, -1, -1):
		if i == 0 and lmax == h[0]:
			res += 1
		if h[i] > lmax:
			res += 1
			lmax = h[i]
	if i == 0 and lmax == h[0]:
		print(res)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	x = a[n - 1]
	ans = 0
	for i in reversed(range(1, n - 1)):
		if x < a[i]:
			ans += 1
			x = a[i]
	if a[0] >= x:
		print(ans + 1)
	else:
		print(-1)


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


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

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

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

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

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	n = inp()
	l = li()
	if l[0] != max(l):
		pr(-1)
		return
	last = defaultdict(int)
	x = set()
	for i in range(n):
		x.add(l[i])
		last[l[i]] = i
	ans = 0
	x = sorted(list(x), reverse=True)
	prev = -1
	for i in x:
		if last[i] < prev:
			continue
		ans += 1
		prev = last[i]
	if last[l[0]] == 0:
		ans -= 1
	pr(ans)
for _ in range(inp()):
	solve()


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	stack = []
	ans = 0
	maxx = -1
	for x in range(n - 1, 0, -1):
		if arr[x] > maxx:
			ans += 1
			maxx = arr[x]
	if arr[0] >= maxx:
		print(ans)
	else:
		print(-1)


t = int(input())
while t:
	ans = 0
	mx = -1
	l = int(input())
	ls = list(map(int, input().split()))[:l]
	if max(ls) != ls[0]:
		print(-1)
	else:
		for i in range(l - 1, 0, -1):
			if ls[i] > mx:
				ans += 1
				mx = ls[i]
		print(ans)
	t -= 1


for t in range(int(input())):
	N = int(input())
	arr = list(map(int, input().split()))
	stck = []
	if arr[0] != max(arr):
		print(-1)
	else:
		for i in range(1, N):
			while stck and stck[-1] <= arr[i]:
				stck.pop()
			stck.append(arr[i])
		print(len(stck))


import math
import os
import collections
from itertools import permutations, combinations
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	m = -1
	for i in range(n - 1, 0, -1):
		if arr[i] > m:
			ans += 1
			m = arr[i]
	if m <= arr[0]:
		print(ans)
	else:
		print(-1)


for _ in range(0, int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	i = 0
	count = 0
	flag = 0
	m = max(l)
	if m != l[0]:
		print(-1)
	else:
		count = 1
		p = l[n - 1]
		for i in range(n - 2, 0, -1):
			if l[i] > p:
				p = l[i]
				count += 1
		print(count)


t = int(input())
for xx in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	ans = arr[0] >= max(arr[1:])
	if not ans:
		print(-1)
	else:
		stack = [arr[1]]
		for i in range(1, n):
			while len(stack) > 0 and stack[-1] <= arr[i]:
				stack.pop()
			stack.append(arr[i])
		print(len(stack))


for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	(max, ans) = (-1, 0)
	for i in range(n - 1, 0, -1):
		if lst[i] > max:
			max = lst[i]
			ans += 1
	if max <= lst[0]:
		print(ans)
	else:
		print('-1')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	i = n - 1
	last = -1
	ans = 0
	while i > 0:
		if arr[i] > last:
			last = arr[i]
			ans += 1
		i = i - 1
	if arr[0] >= last:
		print(ans)
	else:
		print(-1)


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	start = arr[0]
	last = arr[-1]
	arr = arr[1:]
	place = [i for i in range(1, n)]
	zipped_lists = zip(arr, place)
	sorted_pairs = sorted(zipped_lists, reverse=True)
	tuples = zip(*sorted_pairs)
	(arr, place) = [list(tuple) for tuple in tuples]
	if start < arr[0]:
		print(-1)
	else:
		prev = place[0]
		count = 0
		m = 0
		for i in range(1, n - 1):
			if place[i] > prev:
				prev = place[i]
				m = i
				count += 1
		if arr[m] == last:
			print(count + 1)
		else:
			print(-1)
	t -= 1


def func():
	n = int(input())
	ls = list(map(int, input().split()))
	moves = 1
	check = ls[n - 1]
	if check > ls[0]:
		print(-1)
		return
	for i in reversed(ls[1:]):
		if i > check:
			if i > ls[0]:
				print(-1)
				return
			else:
				check = i
				moves += 1
	print(moves)
for t in range(int(input())):
	func()


import heapq
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = a[:]
	b.sort()
	val = b.pop()
	if val != a[0]:
		print(-1)
	else:
		d = defaultdict(list)
		for (i, c) in enumerate(a):
			d[c].append(i)
		ptr = 0
		res = 0
		while ptr < len(a) - 1:
			val = b.pop()
			index = d[val].pop()
			if index < ptr:
				continue
			else:
				ptr = index
				res += 1
		print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	i = len(arr) - 1
	ans = 0
	imp = False
	if arr[0] != max(arr):
		imp = True
	elif arr[0] == arr[-1] == max(arr):
		ans = 1
	else:
		while i > 0:
			j = i - 1
			while j > 0 and arr[i] >= arr[j]:
				j -= 1
			if j == i:
				imp = True
				break
			elif j == 0:
				if arr[j] >= arr[i]:
					ans += 1
					break
				else:
					imp = True
					break
			elif j != -1:
				ans += 1
				i = j
			else:
				imp = True
				break
	if imp:
		print(-1)
	else:
		print(ans)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	ele = A[-1]
	cnt = 0
	ind = N
	for i in range(len(A) - 1, -1, -1):
		if A[i] > ele:
			ele = A[i]
			cnt += 1
			ind = i
	if ele == A[0]:
		if ind == 0:
			print(cnt)
		else:
			print(cnt + 1)
	else:
		print(-1)


t = int(input())
while t:
	n = int(input())
	arr = [int(i) for i in input().split()]
	if arr[0] != max(arr):
		print(-1)
	else:
		count = 0
		maxi = float('-inf')
		for i in range(n - 1, 0, -1):
			if maxi < arr[i]:
				count += 1
				maxi = arr[i]
		print(count)
	t -= 1


for ii in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if max(arr) > arr[0]:
		print(-1)
		continue
	stack = [arr[0]]
	for i in range(1, n):
		if arr[i] < arr[i - 1]:
			stack.append(arr[i])
		else:
			while len(stack) > 1 and arr[i] >= stack[-1]:
				stack.pop()
			stack.append(arr[i])
	print(len(stack) - 1)


def solve(array, n):
	rightMax = [0] * n
	rightMax[-1] = array[-1]
	for i in range(n - 2, -1, -1):
		rightMax[i] = max(rightMax[i + 1], array[i])
	result = 0
	if array[0] < rightMax[1]:
		return -1
	for i in range(2, n):
		if rightMax[i] == rightMax[i - 1]:
			continue
		result += 1
	result += 1
	return result
t_tests = int(input())
for t in range(t_tests):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	print(solve(arr, n))


import sys
input = sys.stdin.readline

def get(ar):
	m = len(ar)
	st = [[10 ** 10, -1]]
	res = []
	for i in range(m):
		while st and st[-1][0] <= ar[i]:
			st.pop()
		res.append(st[-1][1])
		st.append([ar[i], i])
	return res
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = max(a)
	if m != a[0]:
		print(-1)
		continue
	ans = 0
	last = -1
	for i in range(n - 1, 0, -1):
		if a[i] > last:
			ans += 1
			last = a[i]
	print(ans)


try:
	num = int(input())
	for i in range(num):
		num1 = int(input())
		l = list(map(int, input().split()))
		(mx, c) = (-1, 0)
		for i in range(num1 - 1, 0, -1):
			if l[i] > mx:
				c += 1
				mx = l[i]
		if l[0] >= mx:
			print(c)
		else:
			print(-1)
except:
	pass


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	ip = input().split()
	a = [int(i) for i in ip]
	a.insert(0, -1)
	mx = a[n]
	step = 0
	for i in range(n, 0, -1):
		if i != 1 and mx < a[i]:
			mx = a[i]
			step += 1
		elif i == 1 and mx <= a[i]:
			mx = a[i]
			step += 1
	if mx != a[1]:
		print('-1')
	else:
		print(step)


for __ in range(int(input())):
	(MAX, moves) = (-1, 0)
	N = int(input())
	A = list(map(int, input().split()))
	for i in range(N - 1, 0, -1):
		if MAX < A[i]:
			MAX = A[i]
			moves += 1
	print([-1, moves][MAX <= A[0]])


T = int(input())
for x in range(T):
	n = int(input())
	blocks = list(map(int, input().split()))
	i = n - 1
	current = -1
	jump = 0
	while i > 0:
		if current < blocks[i]:
			jump += 1
			current = blocks[i]
		i -= 1
	if blocks[0] >= current:
		print(jump)
	else:
		print(-1)


def hello():
	t = int(input())
	for k in range(t):
		n = int(input())
		list1 = list(map(int, input().split(' ')))
		if n > len(list1):
			print(-1)
		elif list1[0] != max(list1[:n]):
			print(-1)
		else:
			list2 = [[i, list1[i]] for i in range(1, n)]
			list2.sort(key=lambda x: x[1])
			list2 = list2[::-1]
			last = [0, list1[0]]
			step = []
			i = 0
			while last[0] != n - 1:
				if last[1] == list2[i][1]:
					if last[0] < list2[i][0]:
						last = list2[i]
						step.append(list2[i][1])
					i = i + 1
					continue
				if last[0] < list2[i][0]:
					last = list2[i]
					step.append(list2[i][1])
				i = i + 1
			print(len(set(step)))
hello()


tests = int(input())
while tests > 0:
	N = int(input())
	arr = list(map(int, input().split()))
	st = []
	check = arr[0]
	pres = True
	for i in range(1, N):
		if arr[i] <= check:
			while len(st) > 0 and st[-1] <= arr[i]:
				st.pop()
			st.append(arr[i])
		else:
			pres = False
			break
	if pres:
		print(len(st))
	else:
		print(-1)
	tests = tests - 1


tests = int(input())
while tests > 0:
	N = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	mx = -1
	for i in range(N - 1, 0, -1):
		if mx < arr[i]:
			mx = arr[i]
			ans = ans + 1
	if mx <= arr[0]:
		print(ans)
	else:
		print(-1)
	tests = tests - 1


t = int(input())
while t > 0:
	n = int(input())
	a = [int(i) for i in input().split()]
	m = a[n - 1]
	d = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		if m <= a[i]:
			m = a[i]
		d[i] = m
	c = 0
	if d[0] == a[0]:
		m = a[0]
		for i in range(1, n):
			if i == 1 and d[i] == d[0]:
				c += 1
			if d[i] < m:
				c += 1
				m = d[i]
		print(c)
	else:
		print(-1)
	t -= 1


from sys import stdin, stdout

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

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

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

def get_singleInt():
	return int(stdin.readline())

def main():
	testCases = get_singleInt()
	for i in range(testCases):
		n = get_singleInt()
		heights = get_list()
		print(minMoves(heights, n))

def minMoves(heights, n):
	maxx = -1
	ans = 0
	for i in range(n - 1, 0, -1):
		if heights[i] > maxx:
			ans += 1
			maxx = heights[i]
	if heights[0] >= maxx:
		return ans
	return -1
main()


for _ in range(int(input())):
	N = int(input())
	l = list(map(int, input().split()))
	max = -1
	cout = 0
	for x in l[:0:-1]:
		if x > max:
			cout += 1
			max = x
	if l[0] >= max:
		print(cout)
	else:
		print('-1')


for _ in range(int(input())):
	n = int(input())
	dp = [1] * n
	l = list(map(int, input().split()))
	stack = []
	if max(l) != l[0]:
		print(-1)
		continue
	for i in range(1, n):
		while stack and l[stack[-1]] <= l[i]:
			stack.pop()
		if stack:
			dp[i] = max(dp[i], dp[stack[-1]] + 1)
		stack.append(i)
	print(dp[-1])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	max_from_right = [a[-1]]
	max_from_left = a[0]
	cmx = a[-1]
	for h in a[-2::-1]:
		cmx = max(cmx, h)
		max_from_right.append(cmx)
	cmx = a[1]
	for h in a[1:]:
		cmx = max(cmx, h)
		max_from_left = cmx
	max_from_right = list(reversed(max_from_right))
	ans = 0
	if a[0] < max_from_right[1]:
		ans = -1
	else:
		h = max_from_right[1]
		j = 1
		for i in range(2, n):
			if max_from_right[i] != h:
				j += 1
				h = max_from_right[i]
		ans = j
	print(ans)


t = int(input())
for i in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	maxim = 0
	maxpos = 0
	for j in range(0, n):
		if a[j] > maxim:
			maxim = a[j]
			maxpos = j
	if maxpos != 0:
		print(-1)
	else:
		current = n - 1
		j = n - 1
		moves = 0
		while current != 0:
			if a[j] > a[current]:
				a[current] = a[j]
				current = j
				moves += 1
			if a[j] == a[0] and j != 0:
				moves += 1
				current = 0
			j -= 1
		print(moves)


def code(n, arr):
	steps = 0
	curr = arr[-1]
	for i in range(n - 2, -1, -1):
		if arr[i] == curr:
			if i == 0:
				steps += 1
			else:
				continue
		elif arr[i] > curr:
			steps += 1
			curr = arr[i]
	if curr != arr[0]:
		return -1
	return steps
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(code(n, arr))


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if a[0] != max(a):
		print(-1)
	else:
		jumps = 0
		maxi = -1
		for i in range(n - 1, 0, -1):
			if a[i] > maxi:
				jumps += 1
				maxi = a[i]
		print(jumps)


def prog_name():
	n = int(input())
	l = list(map(int, input().split()))
	m = 1000000007
	cnt = 0
	l.reverse()
	j = 0
	if l[-1] != max(l):
		print(-1)
	else:
		for x in range(len(l) - 1):
			if l[x] > j:
				cnt += 1
				j = l[x]
		print(cnt)
T = int(input())
for unique in range(T):
	prog_name()


mod = 1000000007
from sys import stdin, stdout
from collections import defaultdict, Counter, deque
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	li = list(map(int, stdin.readline().split()))
	if max(li) != li[0]:
		print(-1)
		continue
	(ans, maxi) = (0, -1)
	for i in range(n - 1, 0, -1):
		if li[i] > maxi:
			ans += 1
			maxi = li[i]
	if maxi <= li[0]:
		print(ans)
	else:
		print(-1)


def ma(a):
	if len(a) == 1:
		return a[0]
	m = float('-inf')
	for i in a:
		if i > m:
			m = i
	return m
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = float('-inf')
	c = 0
	for i in range(n - 1, 0, -1):
		if a[i] > m:
			c += 1
			m = a[i]
	if a[0] >= m:
		print(c)
	else:
		print(-1)


for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	c = 0
	m = -1
	for i in range(n - 1, 0, -1):
		if a[i] > m:
			c += 1
			m = a[i]
	if a[0] >= m:
		print(c)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	height = list(map(int, input().split()))
	if height[0] < height[-1]:
		print(-1)
	else:
		height = height[::-1]
		cur_max = height[0]
		count = 0
		flag = False
		for i in range(1, n - 1):
			if height[n - 1] < cur_max:
				flag = True
				break
			if height[i] > cur_max:
				count += 1
				cur_max = height[i]
		if flag:
			print(-1)
		else:
			print(count + 1)


num = int(input())
for i in range(num):
	res = []
	n = int(input())
	flag = 0
	ls = list(map(int, input().split()))
	for t in range(1, n):
		if ls[t] > ls[0]:
			print('-1')
			flag = 1
			break
	if flag == 0:
		for p in range(1, n):
			while len(res) and res[-1] <= ls[p]:
				res.pop()
			res.append(ls[p])
		print(len(res))


for m in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	step = 0
	max1 = 0
	for i in range(n - 1, 0, -1):
		if a[i] > max1:
			max1 = a[i]
			step += 1
	if max1 <= a[0]:
		print(step)
	else:
		print(-1)


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	r = [[-1] for i in range(n)]
	if l[0] < l[n - 1]:
		print(-1)
		continue
	l.reverse()
	s = []
	for i in range(n):
		while s and l[s[-1]] < l[i]:
			r[s.pop()].append(i)
		q = []
		while s and l[s[-1]] == l[i]:
			x = s.pop()
			q.append(x)
			r[x].append(i)
		while q:
			s.append(q.pop(0))
		s.append(i)
	res = [max(i) for i in r]
	c = 0
	f = True
	a = 0
	while a != -1:
		c += 1
		if a == n - 1:
			f = False
			print(c - 1)
			break
		a = res[a]
	if f:
		print(-1)


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	ma = -1
	for i in range(n - 1, 0, -1):
		if arr[i] > ma:
			ans += 1
			ma = arr[i]
	if arr[0] == max(arr):
		print(ans)
	else:
		print(-1)
	t -= 1


from collections import defaultdict as dd
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	st = [a[0]]
	for i in range(1, n):
		while st and st[-1] <= a[i]:
			if len(st) == 1 and st[0] == a[i]:
				break
			st.pop()
		if not st:
			break
		st.append(a[i])
	print(len(st) - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	c = 0
	mx = l[-1]
	for i in range(n - 2, 0, -1):
		if l[i] > mx:
			mx = l[i]
			c += 1
	if l[0] >= mx:
		print(c + 1)
	else:
		print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	H = list(map(int, input().split()))
	m = max(H)
	if H[0] != m:
		print(-1)
		continue
	m = H[-1]
	l = [m]
	ind = 0
	for i in H[::-1]:
		if i > l[-1]:
			l.append(i)
	if H.count(H[0]) == 1:
		print(len(l) - 1)
	else:
		print(len(l))


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	num = [lis[-1]]
	for i in range(n - 2, -1, -1):
		if lis[i] >= num[-1]:
			num.append(lis[i])
	if len(num) == 1 or num[-1] != lis[0]:
		print(-1)
	else:
		numd = []
		le = len(num)
		c1 = num.count(lis[0])
		if c1 == 1:
			numd.append(lis[0])
		else:
			numd.append(lis[0])
			numd.append(lis[0])
		for i in range(le - (c1 + 1), -1, -1):
			if numd[-1] != num[i]:
				numd.append(num[i])
		print(len(numd) - 1)


from collections import Counter
t = int(input())
while t != 0:
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	m = max(l)
	s = -1
	if m == l[0]:
		for i in range(n - 1, 0, -1):
			if s < l[i]:
				s = l[i]
				ans = ans + 1
	else:
		ans = -1
	print(ans)
	t = t - 1


try:
	for _ in range(int(input())):
		n = input()
		n = int(n)
		l = list(map(int, input().split(' ')))
		k = max(l)
		h = []
		if k != l[0]:
			print(-1)
		else:
			d = 1
			for i in range(1, n):
				h.append(l[0] - l[i])
			f = h[len(h) - 1]
			for i in range(0, len(h)):
				if h[len(h) - 1 - i] < f:
					f = h[len(h) - 1 - i]
					d = d + 1
			print(d)
except:
	pass


def check(n, a):
	data = []
	for i in range(1, n):
		if a[0] < a[i]:
			return -1
	for i in range(1, n):
		while len(data) and data[-1] <= a[i]:
			data.pop()
		data.append(a[i])
	return len(data)
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(check(n, a))


T = int(input())
while T > 0:
	T -= 1
	N = int(input())
	arr = [int(x) for x in input().split(' ')]
	ans = []
	status = True
	for index in range(1, N):
		if arr[index] > arr[0]:
			print(-1)
			status = False
			break
	if status:
		for i in range(1, N):
			while len(ans) > 0 and ans[-1] <= arr[i]:
				ans.pop()
			ans.append(arr[i])
		print(len(ans))


import sys
import math
import heapq
from collections import defaultdict as dd
from collections import OrderedDict as od
from collections import deque
from itertools import permutations as pp
from itertools import combinations as cc
from sys import stdin
from functools import cmp_to_key
from functools import lru_cache
from bisect import bisect_left as bs_l
from bisect import bisect_right as bs_r
input = sys.stdin.readline
mod = 10 ** 9 + 7
sys.setrecursionlimit(10 ** 5)
T = int(input())
for _ in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	mx = max(arr)
	if arr[0] != mx:
		print(-1)
		continue
	d = dd(list)
	c = 0
	for i in arr:
		d[i].append(c)
		c += 1
	ll = []
	arr.sort(reverse=True)
	for i in arr:
		if i == mx:
			ll += [d[i][0], d[i][-1]]
		else:
			ll += [d[i][-1]]
	ans = 0
	mx = 0
	for i in range(1, len(ll)):
		if ll[i] > mx:
			mx = ll[i]
			ans += 1
	print(ans)


t = int(input())
for test in range(t):
	n = int(input())
	num = list(map(int, input().split()))
	dp = [0] * n
	i = n - 2
	mx = num[-1]
	mp = 0
	while i > 0:
		if num[i] > mx:
			dp[i] = mp + 1
			mp = dp[i]
			mx = num[i]
		elif num[i] == mx:
			dp[i] = mp
		else:
			dp[i] = -1
		i -= 1
	if num[i] >= mx:
		dp[i] = mp + 1
	else:
		dp[i] = -1
	print(dp[0])


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if 1:
		ma = l[-1]
		ans = 1
		for i in range(n - 1, 0, -1):
			if ma < l[i]:
				ma = l[i]
				ans += 1
		if ma <= l[0]:
			print(ans)
		else:
			print(-1)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	max_ele = -1
	count = 0
	for i in range(n - 1, 0, -1):
		if arr[i] > max_ele:
			count += 1
			max_ele = arr[i]
	if arr[0] >= max_ele:
		print(count)
	else:
		print('-1')


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	r = a[::-1]
	mval = []
	maxi = 0
	for i in range(n):
		if r[i] > maxi:
			maxi = r[i]
		mval.append(maxi)
	mval = mval[::-1]
	i = 0
	jump = 0
	s = 0
	while i < n - 1:
		if s == 0 and a[i] >= mval[i + 1]:
			s = 1
			jump += 1
		elif s == 1 and a[i] > mval[i + 1]:
			s = 0
			i -= 1
		elif s == 0 and a[i] < mval[i]:
			jump = -1
			break
		i += 1
	print(jump)


t = int(input())
while t > 0:
	n = int(input())
	nums = [int(x) for x in input().split()]
	first = nums[0]
	cot = 0
	for i in range(len(nums)):
		if nums[i] > first:
			cot = -1
	if cot == -1:
		print(cot)
		t -= 1
		continue
	s = []
	for i in range(1, n):
		while len(s) > 0 and s[-1] <= nums[i]:
			s.pop()
		s.append(nums[i])
	ans = 0
	while len(s) > 0:
		ans += 1
		s.pop()
	print(ans)
	t -= 1