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: interview

Starter code:

Solutions:
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))

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))

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))

# cook your dish here
        
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))


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))

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")
    


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 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))

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 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:]))



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

# cook your dish here
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())
	#k,r=map(int,input().split())
	l=list(map(int,input().split()))
	print(res(l))

# cook your dish here
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
    #elif(i>start+int((end-start)/2)):
    #    return 1+rec(arr,i+1,end)
    #elif(i<start+int((end-start)/2)):
    #    return 1+rec(arr,start,i)
    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 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))

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))


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))






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))

# cook your dish here
for _ in range(int(input())):
    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))

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))



# cook your dish here
#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())
	#k,r=map(int,input().split())
	l=list(map(int,input().split()))
	print(res(l))

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))
        


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 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 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)








# N,M = map(int, input().split())
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
    # print("top: ", topi, topv)
    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)