In ChefLand, there is a mountain range consisting of $N$ hills (numbered $1$ through $N$) in a straight line. Let's denote the height of the $i$-th hill from the left by $h_i$.
Ada is working on the water supply system of ChefLand. On some of the hills, she wants to place water reservoirs; then, for each reservoir, she will decide in which direction the water should flow from it — either to the left or to the right (water may not flow in both directions from the same reservoir). From a reservoir on a hill with height $h$, water flows in the chosen direction until it reaches the first hill that is strictly higher than $h$; all hills before this hill (including the hill containing the reservoir) are therefore supplied with water.
For example, suppose we have hills with heights $[7, 2, 3, 5, 8]$. If we place a reservoir on the hill with height $5$, and pump water from it to the left, then the hills with heights $2$, $3$ and $5$ are supplied with water.
Help Ada find the minimum numer of reservoirs needed to provide water to all the hills if she chooses the directions optimally.

-----Input-----
- 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 $h_1, h_2, \dots, h_N$.

-----Output-----
For each test case, print a single line containing one integer — the minimum required number of reservoirs.

-----Constraints-----
- $2 \le N \le 10^5$
- $1 \le h_i \le 10^9$ for each valid $i$
- $h_i \neq h_j $ for any valid $i \neq j$
- the sum of $N$ over all test cases does not exceed $5 \cdot 10^5$

-----Example Input-----
1
6
4 16 32 6 8 2

-----Example Output-----
2    

-----Explanation-----
Example case 1: We can place reservoirs on the second and third hill, pumping water to the left and right respectively.

Difficulty: HARD
Tags: Data structures

Range queries

Segment trees revisited
Skill types: Data structures

Range queries

Starter code:

Solutions:
def reservoirs(lhills):
	hmax = lhills[0]
	for i in lhills:
		if i > hmax:
			hmax = i
	j = lhills.index(hmax)
	if j == 0 or j == len(lhills) - 1:
		return 1
	else:
		return 1 + min(reservoirs(lhills[:j]), reservoirs(lhills[j + 1:]))
t = int(input())
for _ in range(t):
	n = int(input())
	lhills = list(map(int, input().strip().split()))
	print(reservoirs(lhills))


import numpy as np

def modbin(arr):
	n = len(arr)
	if n == 0:
		return 0
	max_id = np.argmax(arr)
	if max_id == 0 or max_id == n - 1:
		return 1
	else:
		return min(modbin(arr[0:max_id]), modbin(arr[max_id + 1:n])) + 1
for i in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	print(modbin(h))


import math

def res(n):
	l = len(n)
	maxx = max(n)
	i = 0
	i = n.index(maxx)
	if i == 0 or i == l - 1:
		return 1
	else:
		return 1 + min(res(n[:i]), res(n[i + 1:]))
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	print(res(l))


def solve(ar):
	max = 0
	posn = -1
	for i in range(len(ar)):
		if ar[i] > max:
			max = ar[i]
			posn = i
	if posn == 0 or posn == len(ar) - 1:
		return 1
	return 1 + min(solve(ar[:posn]), solve(ar[posn + 1:]))
t = int(input())
for i in range(t):
	n = int(input())
	h = list(map(int, input().split()))
	z = solve(h)
	print(z)


def res(arr):
	max_a = max(arr)
	if len(arr) == 0:
		return 0
	if arr[0] == max_a or arr[-1] == max_a:
		return 1
	else:
		index = arr.index(max_a)
		count_1 = res(arr[:index])
		count_2 = res(arr[index + 1:])
	return min(count_2, count_1) + 1
t = int(input())
for a in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	count = 0
	max_a = max(arr)
	mid = len(arr) // 2
	count = res(arr)
	print(count)


for i in range(int(input())):
	n = int(input())
	count = 0
	hill = list(map(int, input().split()))

	def res(hills):
		maxval = max(hills)
		maxpos = hills.index(maxval)
		left = list()
		right = list()
		if maxpos is 0 or maxpos is len(hills) - 1:
			return 1
		for j in range(maxpos):
			left.append(hills[j])
		for j in range(maxpos + 1, len(hills)):
			right.append(hills[j])
		return 1 + min(res(right), res(left))
	print(res(hill))


def divide(A, l, r):
	m = -1
	maxi = 0
	for i in range(l, r + 1):
		if A[i] > maxi:
			maxi = A[i]
			m = i
	if m == l or m == r:
		return 1
	else:
		return 1 + min(divide(A, l, m - 1), divide(A, m + 1, r))
t = int(input())
while t > 0:
	n = int(input())
	A = [int(x) for x in input().split()]
	k = divide(A, 0, n - 1)
	print(k)
	t -= 1


def select_hill(hills):
	m = hills.index(max(hills))
	if m == 0 or m == len(hills) - 1:
		return 1
	else:
		return 1 + min(select_hill(hills[:m]), select_hill(hills[m + 1:]))
t = int(input())
for _ in range(t):
	n = int(input())
	hills = list(map(int, input().split()))
	print(select_hill(hills))


def hill(lst):
	maxm = lst.index(max(lst))
	if maxm == 0 or maxm == len(lst) - 1:
		return 1
	else:
		return 1 + min(hill(lst[:maxm]), hill(lst[maxm + 1:]))
t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split(' ')))
	print(hill(lst))


T = int(input())

def maxk(arr, start, end):
	maxno = arr[start]
	maxi = start
	for i in range(start, end):
		if arr[i] > maxno:
			maxno = arr[i]
			maxi = i
	return maxi

def rec(arr, start, end):
	i = maxk(arr, start, end)
	if i == start or i == end - 1:
		return 1
	else:
		return 1 + min(rec(arr, i + 1, end), rec(arr, start, i))
for t in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	start = 0
	end = n
	count = rec(arr, start, end)
	print(count)


def solve(h):
	x = h.index(max(h))
	if x == 0 or x == len(h) - 1:
		return 1
	else:
		return min([solve(h[x + 1:]), solve(h[:x])]) + 1
t = int(input())
for i in range(t):
	n = int(input())
	h = list(map(int, input().split()))
	print(solve(h))


def result(a):
	ind = a.index(max(a))
	n = len(a)
	if ind == 0 or ind == n - 1:
		return 1
	else:
		return 1 + min(result(a[0:ind]), result(a[ind + 1:]))
tc = int(input())
while tc > 0:
	n = int(input())
	hill = list(map(int, input().split()))
	print(result(hill))
	tc -= 1


def helper(l, count):
	le = len(l)
	if not l:
		return count
	count += 1
	m = l.index(max(l))
	if le - 1 == m or m == 0:
		return count
	x = helper(l[:m], count)
	y = helper(l[m + 1:], count)
	if x < y:
		return x
	else:
		return y

def func():
	n = int(input())
	l = list(map(int, input().strip().split()))
	print(helper(l, 0))
t = int(input())
for i in range(t):
	func()


def rec(h):
	maxi = max(h)
	ind = h.index(maxi)
	if ind == 0 or ind == len(h) - 1:
		return 1
	else:
		return min(rec(h[:ind]), rec(h[ind + 1:])) + 1
for _ in range(int(input())):
	n = int(input())
	h = [int(n) for n in input().split()]
	print(rec(h))


def fun(b):
	i = b.index(max(b))
	n = len(b)
	if i == 0 or i == n - 1:
		return 1
	else:
		return 1 + min(fun(b[0:i]), fun(b[i + 1:]))
for _ in range(int(input())):
	a = int(input())
	count = 0
	b = [int(x) for x in input().split()]
	print(fun(b))


def large(a, i, j):
	b = i
	maxo = a[i]
	t = i
	while b <= j:
		if a[b] > maxo:
			maxo = a[b]
			t = b
		b = b + 1
	return t

def f(a, i, j, count):
	p = large(a, i, j)
	if p == i or p == j:
		count = count + 1
		return count
	else:
		return min(f(a, i, p - 1, count + 1), f(a, p + 1, j, count + 1))
t = int(input())
for x in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(f(a, 0, n - 1, 0))


def get_max_index(heights, s, e):
	max_val = heights[s]
	index = s
	for i in range(s + 1, e + 1):
		if heights[i] > max_val:
			max_val = heights[i]
			index = i
	return index

def get_min_num_of_reserviors(heights, i, j):
	if i > j:
		return 0
	elif i == j:
		return 1
	else:
		k = get_max_index(heights, i, j)
		if k == i or k == j:
			return 1
		else:
			return 1 + min(get_min_num_of_reserviors(heights, i, k - 1), get_min_num_of_reserviors(heights, k + 1, j))
T = int(input())
while T:
	N = int(input())
	heights = list(map(int, input().split()))
	print(get_min_num_of_reserviors(heights, 0, N - 1))
	T -= 1


t = int(input())
for i in range(t):
	n = int(input())
	h = list(map(int, input().split()))

	def res(a):
		n = len(a)
		max1 = max(a)
		ind = 0
		ind = a.index(max1)
		if ind == 0 or ind == n - 1:
			return 1
		else:
			return 1 + min(res(a[:ind]), res(a[ind + 1:]))
	print(res(h))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))

	def func(l):
		m = max(l)
		m = l.index(m)
		if m == len(l) - 1 or m == 0:
			return 1
		ll = l[:m]
		rl = l[m + 1:]
		return 1 + min(func(rl), func(ll))
	print(func(l))


from functools import lru_cache
kases = int(input())
while kases > 0:
	kases = kases - 1
	T = int(input())
	arr = list(map(int, input().split(' ')))

	@lru_cache(maxsize=500)
	def ans(i, j):
		if i > j:
			return 0
		val = arr[i]
		x = i
		k = i
		while k <= j:
			if arr[k] > val:
				val = arr[k]
				x = k
			k = k + 1
		if x == i or x == j:
			return 1
		return 1 + min(ans(i, x - 1), ans(x + 1, j))
	print(ans(0, T - 1))


T = int(input())

def func(l):
	m = l.index(max(l))
	if m == 0 or m == len(l) - 1:
		return 1
	else:
		return 1 + min(func(l[:m]), func(l[m + 1:]))
for i in range(T):
	N = int(input())
	l = list(map(int, input().split()))
	print(func(l))


def sol(A):
	ci = A.index(max(A))
	if ci == 0 or ci == len(A) - 1:
		return 1
	else:
		return 1 + min(sol(A[:ci]), sol(A[ci + 1:]))
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	count = 0
	print(sol(A))


def res(h):
	i = 0
	m = 0
	for (ind, val) in enumerate(h):
		if val > m:
			m = val
			i = ind
	l = len(h)
	if i == 0 or i == l - 1:
		return 1
	return 1 + min([res(h[i + 1:]), res(h[:i])])
for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	print(res(h))


def find_max(A, s, e):
	m = 0
	m_index = s
	for i in range(s, e + 1):
		if A[i] > m:
			m = A[i]
			m_index = i
	return m_index

def solution(A, s, e, ans):
	m_index = find_max(A, s, e)
	if m_index == s or m_index == e:
		ans = ans + 1
		return ans
	return min(solution(A, m_index + 1, e, ans + 1), solution(A, s, m_index - 1, ans + 1))
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	ans = solution(A, 0, N - 1, 0)
	print(ans)


def f(height):
	ind = height.index(max(height))
	n = len(height)
	if ind == 0 or ind == n - 1:
		return 1
	else:
		return 1 + min(f(height[0:ind]), f(height[ind + 1:]))
test = int(input())
while test:
	n = int(input())
	h = list(map(int, input().split()))
	print(f(h))
	test = test - 1


def count(a):
	m = a.index(max(a))
	n = len(a)
	if n == 1:
		return 1
	elif m == 0 or m == n - 1:
		return 1
	else:
		return 1 + min(count(a[:m]), count(a[m + 1:]))
t = int(input())
for itr in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(count(a))


def solve(l):
	m = l.index(max(l))
	if m == 0 or m == len(l) - 1:
		return 1
	return 1 + min(solve(l[0:m]), solve(l[m + 1:]))
tc = int(input())
for test in range(tc):
	n = int(input())
	l = list(map(int, input().split()))
	print(solve(l))


import sys

def countr(s):
	highest = max(s)
	indexh = s.index(highest)
	n = len(s)
	if indexh == 0 or indexh == n - 1:
		return 1
	left = s[:indexh]
	right = s[indexh + 1:]
	return min(countr(left), countr(right)) + 1

def main():
	T = int(input())
	D = {}
	for i in range(T):
		N = int(input())
		H = [int(item) for item in input().split()]
		D[i] = (N, H)
	for (k, v) in D.items():
		(N, H) = v
		print(countr(H))
	return 0
main()


t = int(input())
for _ in range(t):
	n = int(input())
	lis = list(map(int, input().split()))

	def f(a, b):
		m = a
		for i in range(a, b + 1):
			if lis[m] < lis[i]:
				m = i
		if m == a or m == b:
			return 1
		return 1 + min(f(a, m - 1), f(m + 1, b))
	print(f(0, n - 1))


import math

def res(n):
	l = len(n)
	maxx = max(n)
	i = n.index(maxx)
	if i == 0 or i == l - 1:
		return 1
	else:
		return 1 + min(res(n[:i]), res(n[i + 1:]))
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(res(l))


import sys
sys.setrecursionlimit(10000)

def func(arr, c=0):
	if arr:
		c += 1
		m = 0
		for i in range(len(arr)):
			if arr[i] > m:
				j = i
				m = arr[i]
		if j == 0 or j == len(arr) - 1:
			return c
		else:
			a = func(arr[:j], c)
			b = func(arr[j + 1:], c)
		return min(a, b)
	else:
		return c
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	c = func(arr)
	print(c)


def find(ar):
	mx = max(ar)
	ind = ar.index(mx)
	n = len(ar)
	if ind == 0 or ind == n - 1:
		return 1
	else:
		return 1 + min(find(ar[0:ind]), find(ar[ind + 1:]))
t = int(input())
for _ in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	print(find(ar))


def f(l, n, c, k):
	x = 0
	if k == n:
		return c
	m = -1
	for i in range(k, n):
		if m < l[i]:
			m = l[i]
			x = i
	c += 1
	(a, b) = (f(l, n, c, x + 1), f(l, x, c, k))
	if a < b:
		return a
	else:
		return b

def f1(l: list, s: int, e: int):
	m = -1
	k = -1
	for i in range(s, e + 1):
		if l[i] > m:
			m = l[i]
			k = i
	if m in (l[s], l[e]):
		return 1
	else:
		return 1 + min(f1(l, s, k - 1), f1(l, k + 1, e))
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	(c, k) = (0, 0)
	print(f1(a, 0, n - 1))


def res(h):
	i = h.index(max(h))
	l = len(h)
	if i == 0 or i == l - 1:
		return 1
	return 1 + min([res(h[i + 1:]), res(h[:i])])
for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	print(res(h))


def p(l):
	n2 = len(l)
	m = l.index(max(l))
	if m < 1 or m > n2 - 2:
		return 1
	return 1 + min(p(l[:m]), p(l[m + 1:]))
t = int(input())
solution = []
for r in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	solution.append(p(a))
print(*solution, sep='\n')


t = int(input())

def pump(arr, n):
	count = 0
	maxHeight = arr.index(max(arr))
	if maxHeight == 0 or maxHeight == n - 1:
		return 1
	leftRes = pump(arr[:maxHeight], maxHeight)
	rightRes = pump(arr[maxHeight + 1:], n - maxHeight - 1)
	if leftRes > rightRes:
		count = count + rightRes + 1
	else:
		count = count + leftRes + 1
	return count
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	result = pump(arr, n)
	print(result)


def water(hills):
	currIndex = hills.index(max(hills))
	n = len(hills)
	if currIndex == 0 or currIndex == n - 1:
		return 1
	return 1 + min(water(hills[:currIndex]), water(hills[currIndex + 1:]))
t = int(input())
for tcase in range(t):
	n = int(input())
	nums = [int(el) for el in input().split()]
	print(water(nums))


def solve(st, ed):
	if st > ed:
		return 0
	if st == ed:
		return 1
	ab = max(b[st:ed + 1])
	if ab[1] == st or ab[1] == ed:
		return 1
	return 1 + min(solve(st, ab[1] - 1), solve(ab[1] + 1, ed))
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [[a[i], i] for i in range(n)]
	print(solve(0, n - 1))


def get_count(hills):
	max_ = hills.index(max(hills))
	if not max_ or max_ == len(hills) - 1:
		return 1
	return 1 + min(get_count(hills[:max_]), get_count(hills[max_ + 1:]))
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(get_count(arr))


def coun(c, a):
	n = len(a)
	m = a.index(max(a))
	if n == 1:
		return c + 1
	elif m == 0 or m == n - 1:
		return c + 1
	c1 = coun(c + 1, a[m + 1:])
	c2 = coun(c + 1, a[:m])
	return min(c1, c2)
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	print(coun(c, a))


def solve(a, l, r):
	pos = None
	for i in range(l, r + 1):
		if pos == None or a[i] >= a[pos]:
			pos = i
	if pos == l or pos == r:
		return 1
	return 1 + min(solve(a, l, pos - 1), solve(a, pos + 1, r))

def main():
	t = int(input())
	while t:
		n = int(input())
		str = input()
		a = [int(x) for x in str.split()]
		print(solve(a, 0, n - 1))
		t -= 1
main()


def get(l):
	inde = l.index(max(l))
	if inde == 0 or inde == len(l) - 1:
		return 1
	return 1 + min(get(l[0:inde]), get(l[inde + 1:]))
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	print(get(l))


T = int(input())
from copy import copy

def dfs(lst):
	topi = -1
	topv = 0
	for (i, e) in enumerate(lst):
		if topv < e:
			topv = e
			topi = i
	if topi == 0 or topi == len(lst) - 1:
		return 1
	else:
		return 1 + min(dfs(lst[:topi]), dfs(lst[topi + 1:]))
for t in range(T):
	N = int(input())
	H = list(map(int, input().split()))
	ans = dfs(H)
	print(ans)


def func(l):
	ind = l.index(max(l))
	n = len(l)
	if ind == 0 or ind == n - 1:
		return 1
	else:
		return 1 + min(func(l[ind + 1:]), func(l[:ind]))
for i in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	print(func(l))


def rec(h, low, high):
	maxIndex = low
	for i in range(low + 1, high + 1):
		if h[i] > h[maxIndex]:
			maxIndex = i
	if maxIndex == low or maxIndex == high:
		return 1
	else:
		return 1 + min(rec(h, low, maxIndex - 1), rec(h, maxIndex + 1, high))
t = int(input())
for T in range(t):
	n = int(input())
	h = list(map(int, input().split()))
	print(rec(h, 0, n - 1))


from sys import stdin
max_val = int(10000000000000.0)
min_val = int(-10000000000000.0)

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

def read_ints():
	return [int(x) for x in stdin.readline().split()]

def read_str():
	return input()

def read_strs():
	return [x for x in stdin.readline().split()]

def needed(hts):
	maxi = hts.index(max(hts))
	if maxi == 0 or maxi == len(hts) - 1:
		return 1
	else:
		return 1 + min(needed(hts[:maxi]), needed(hts[maxi + 1:]))
nb_test = read_int()
for _ in range(nb_test):
	nb_hills = read_int()
	heights = read_ints()
	print(needed(heights))


def water(l):
	m = l.index(max(l))
	if m == 0 or m == len(l) - 1:
		return 1
	return 1 + min(water(l[0:m]), water(l[m + 1:]))
try:
	tc = int(input())
	for test in range(tc):
		n = int(input())
		l = list(map(int, input().split()))
		print(water(l))
except:
	pass


T = int(input())

def Number(A):
	if len(A) == 0:
		return 0
	elif len(A) == 1:
		return 1
	x = max(A)
	if A.index(x) == 0 or A.index(x) == len(A) - 1:
		return 1
	return 1 + min(Number(A[:A.index(x)]), Number(A[A.index(x) + 1:]))
for i in range(T):
	N = int(input())
	H = list(map(int, input().split()))
	print(Number(H))


for i in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	arr = []
	arr.append(h)
	l = 0
	bre = 0
	while True:
		l = l + 1
		c = []
		for m in arr:
			x = m.index(max(m))
			p = len(m)
			if x == 0 or x == p - 1:
				bre += 1
				break
			else:
				c.append(m[:x])
				c.append(m[x + 1:])
		arr = c[:]
		if bre > 0:
			break
	print(l)


def main():
	t = int(input())
	for z in range(t):
		n = int(input())
		li = list(map(int, input().split()))
		print(no_cal(li))

def no_cal(li):
	index = li.index(max(li))
	if index == 0 or index == len(li) - 1:
		return 1
	else:
		return 1 + min(no_cal(li[:index]), no_cal(li[index + 1:]))
main()


def sol(A):
	ci = A.index(max(A))
	if ci == 0 or ci == len(A) - 1:
		return 1
	return 1 + min(sol(A[0:ci]), sol(A[ci + 1:]))
for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	print(sol(l))


import sys

def getMaxReservoir(sortedHills, pos, left, right):
	(heigth, index) = sortedHills[pos]
	while index < left or index >= right:
		pos += 1
		(heigth, index) = sortedHills[pos]
	diff = min(right - index, index - left + 1)
	if diff < 3:
		return diff
	return 1 + min(getMaxReservoir(sortedHills, pos + 1, index + 1, right), getMaxReservoir(sortedHills, pos + 1, left, index))
t = int(sys.stdin.readline())
while t > 0:
	n = int(sys.stdin.readline())
	hs = list(map(int, sys.stdin.readline().split()))
	hsSorted = []
	for i in range(0, n):
		hsSorted.append((hs[i], i))
	hsSorted.sort(key=lambda tup: tup[0], reverse=True)
	print(getMaxReservoir(hsSorted, 0, 0, n))
	t -= 1


t = int(input())

def maxcof(arr):
	i = 0
	max = 0
	for i in range(1, len(arr)):
		if arr[i] > arr[max]:
			max = i
	return max

def splitarr(arr):
	x = maxcof(arr)
	temp1 = arr[x + 1:]
	temp2 = arr[:x]
	if len(temp1) == 0 or len(temp2) == 0:
		return 1
	else:
		m = min(splitarr(temp1), splitarr(temp2))
		return m + 1
for i in range(t):
	n = int(input())
	count = 0
	inp = list(map(int, input().split()))
	print(splitarr(inp))


for _ in range(0, int(input())):
	N = int(input())
	count = 0
	hillsH = list(map(int, input().split()))

	def FindAns(hills):
		maxIndex = 0
		maxNum = max(hills)
		maxIndex = hills.index(maxNum)
		listRight = []
		listLeft = []
		if maxIndex == 0 or maxIndex == len(hills) - 1:
			return 1
		for i in range(0, maxIndex):
			listLeft.append(hills[i])
		for i in range(maxIndex + 1, len(hills)):
			listRight.append(hills[i])
		return 1 + min(FindAns(listLeft), FindAns(listRight))
	print(FindAns(hillsH))


def max_count(arr):
	x = arr.index(max(arr))
	if x == 0 or x == len(arr) - 1:
		return 1
	else:
		return min(max_count(arr[:x]), max_count(arr[x + 1:])) + 1
for _ in range(int(input())):
	count = int(input())
	lis = list(map(int, input().split()))
	print(max_count(lis))


def res(a):
	ind = a.index(max(a))
	n = len(a)
	if ind == 0 or ind == n - 1:
		return 1
	else:
		return 1 + min(res(a[0:ind]), res(a[ind + 1:]))
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = [int(x) for x in input().split()]
	print(res(a))


def solve(a):
	m = a.index(max(a))
	if m == 0 or m == len(a) - 1:
		return 1
	return 1 + min(solve(a[0:m]), solve(a[m + 1:]))
for _ in range(int(input())):
	n = int(input())
	a = [int(a) for a in input().split()]
	print(solve(a))


def res(a):
	ind = a.index(max(a))
	n = len(a)
	if ind == 0 or ind == n - 1:
		return 1
	else:
		return 1 + min(res(a[0:ind]), res(a[ind + 1:]))
t = int(input())
for _ in range(0, t):
	n = int(input())
	lst = list(map(int, input().split()))
	print(res(lst))


def res(a):
	ind = a.index(max(a))
	n = len(a)
	if ind == 0 or ind == n - 1:
		return 1
	else:
		return 1 + min(res(a[0:ind]), res(a[ind + 1:]))
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	print(res(a))


def func(a):
	k = a.index(max(a))
	n = len(a)
	if k == 0 or k == n - 1:
		return 1
	else:
		return 1 + min(func(a[0:k]), func(a[k + 1:]))
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(func(a))


import numpy as np

def calc(h):
	if len(h) == 0:
		return 0
	ind = np.argmax(h)
	if ind == 0 or ind == len(h) - 1:
		return 1
	else:
		return min(calc(h[0:ind]), calc(h[ind + 1:len(h)])) + 1
t = int(input())
for i in range(t):
	n = int(input())
	h = list(map(int, input().split()))
	val = calc(h)
	print(val)


t = int(input())

def largest(a, d, n):
	max = d
	for i in range(d, n):
		if a[i] > a[max]:
			max = i
	return max

def pump(a, d, n):
	if d == n:
		return 0
	cur = largest(a, d, n)
	if cur == d or cur == n - 1:
		return 1
	else:
		e = pump(a, d, cur)
		f = pump(a, cur + 1, n)
		return 1 + min(e, f)
while t:
	n = int(input())
	a = list(map(int, input().split()))
	print(pump(a, 0, n))
	t = t - 1


def min_pumps(lst):
	if not lst:
		return 0
	r = 0
	for i in range(len(lst)):
		if lst[i] > lst[r]:
			r = i
	if r == 0 or r == len(lst):
		return 1
	return 1 + min(min_pumps(lst[:r]), min_pumps(lst[r + 1:]))
for _ in range(int(input())):
	input()
	hills = list(map(int, input().split()))
	print(min_pumps(hills))


def reservoir(a):
	ind = a.index(max(a))
	if ind == len(a) - 1 or ind == 0:
		return 1
	else:
		return min(reservoir(a[:ind]), reservoir(a[ind + 1:])) + 1
for t in range(int(input())):
	n = int(input())
	a = []
	for i in input().split():
		a.append(int(i))
	print(reservoir(a))


def find(l, h, a):
	m = -1
	idx = 0
	for i in range(l, h + 1):
		if m < a[i]:
			m = a[i]
			idx = i
	return idx

def solve(l, h, a):
	m = find(l, h, a)
	if l == h:
		return 1
	if m == l or m == h:
		return 1
	else:
		return 1 + min(solve(l, m - 1, a), solve(m + 1, h, a))
for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(solve(0, n - 1, l))


def short_path(h, lower, upper, maxi, dic):
	if lower == maxi or upper == maxi:
		return 1
	else:
		return 1 + min(short_path(h, maxi + 1, upper, dic[max(h[maxi + 1:upper + 1])], dic), short_path(h, lower, maxi - 1, dic[max(h[lower:maxi])], dic))
t = int(input())
for it in range(t):
	size = int(input())
	h = list(map(int, input().split()))
	dic = dict()
	for i in range(len(h)):
		dic[h[i]] = i
	print(short_path(h, 0, len(h) - 1, dic[max(h)], dic))


def water(left, right, h):
	ma = 0
	for i in range(left, right + 1):
		if h[i] > ma:
			ma = h[i]
			mai = i
	if mai == left or mai == right:
		return 1
	else:
		return 1 + min(water(left, mai - 1, h), water(mai + 1, right, h))
t = int(input())
while t:
	n = int(input())
	h = list(map(int, input().split()))
	ans = water(0, n - 1, h)
	print(ans)
	t = t - 1


def find_res(heights):
	pos = heights.index(max(heights))
	if pos == len(heights) - 1 or pos == 0:
		return 1
	return 1 + min(find_res(heights[:pos]), find_res(heights[pos + 1:]))
for _ in range(int(input())):
	n = int(input())
	heights = list(map(int, input().strip().split()))
	print(find_res(heights))


def minres(h, n):
	i = h.index(max(h))
	return 1 if i == 0 or i == n - 1 else min(minres(h[:i], i), minres(h[i + 1:], n - i - 1)) + 1
for _ in range(int(input())):
	n = int(input())
	h = list(map(int, input().split()))
	print(minres(h, n))