def maxi(T):
    if T==[]:
        return None
    if T[1]==[] and T[2]==[]:return T[0]
    if T[1]==[] :return max(maxi(T[2]),T[0])
    if T[2]==[] :return max(maxi(T[1]),T[0])
    return max(maxi(T[1],maxi(T[2]),T[0])
                             
def getval(T):
    if T==[]:
        return None
    return [T[0]]+getval(T[1])+getval(T[2])
def build(T):
    if not T : return []
    N=len(T)//2
    L=T[:N]
    R=T[N+1:]
    return [T[N],build(L),build(R)]
    
def insert(T, x):

    if not T:
        return [x, [], []]  
    if x < T[0]:

        T[1] = insert(T[1], x)
    else:

        T[2] = insert(T[2], x)
def find(T,x):
    if not T:
        return False
    if x==T[0]:
        return True
    else: return find(T[1],x) or find(T[2],x)
def findR(T,x):
    if T==[]: return False
    if T[0]==x : return True
    if x<T[0] : return findR(T[1])
    return findR(T[2])
    
def infixe(A):
    if A!=[]:
        infixe(A[1])
        print(A[0],end=' ')
        infixe(A[2])
def Nfois(T,x):
    if A==[]:return 0
    if A[0]==x: return 1 + Nfois(T[1],x) + Nfois(T[2],x)
    return Nfois(T[1],x) + Nfois(T[2],x)

def Nfoid(T,x):
    if A==[]:return 0
    if A[0]==x: return 1 + Nfois(T[1],x) + Nfois(T[2],x)
    if x<T[0] : return NfoisR(A[1],x)
    return NfoisR(A[2],x)
def ABR1(T,mini=float('-inf'),maxi=float('inf')):
    if A==[]: return True
    if not mini<A[0]<maxi: return False
    return ABR1(A[1],mini,A[0]) and ABR1(A[2],A[0],maxi)
def ABR(T):
    if T==[0]: return True
    if T[1]==[] and T[2]==[] : return True
    if A[1]==[]: return A[0]<=Mini(A[2]) and A
def Tri(L):
    A=[] #abr
    for x in L:
        insert(A,x)
    return infixe(A)