def AlgoIt(A,x,y,k):
    currx=x
    curry=y
    stacky=[]
    stacka=[]
    stackVal=[]
    nextx=None
    nexty=None
    lasty=None
    ret=None
    val=0
    while(currx<=curry) or (not stacky):
        if(currx<=curry):
            z=int((x+y)/2)
            if (A[z] == k):
                val = 1
            else:
                val = 0
            stackVal.append(val)
            stacky.append(curry)
            nextx=curry
            nexty=z+1
        else:
            curry=stacky.pop()
            if(lasty!=curry):
                a=ret
                z=lasty+1
                if(A[z]==k):
                    val=1
                else:
                    val=0
                stackVal.append(val)
                stacka.append(a)
                nextx=z+1
                nexty=curry
            else:
                val=stackVal.pop()
                a=stacka.pop()
                b=ret
                val=val+a+b
                stackVal.pop()
                stacka.pop()
                stacky.pop()
                nexty=currx-1
                ret=val
        lasty=curry
        curry=nexty
        currx=nextx
    return val


def AlgoRic(A,x,y,k):
    val=0
    if(x<=y):
        z=int((x+y)/2)
        if(A[z]==k):
            val=1
        a=AlgoRic(A,x,z-1,k)
        if(a>val):
            val=a+val
        b=AlgoRic(A,z+1,y,k)
        val=val+a+b
    return val

def main():
    array=[3,2,1,7,15,12,23,33]
    print(AlgoRic(array,0,7,12))
    print(AlgoIt(array,0,7,12))

if __name__ == '__main__':
    main()