#an iterative solution for (d) - Runs in O(log n) time

def find_steady_side(L, side='L'):
    ''' find L[i]==i or return None, side = 'L' or 'R' for leftmost/rightmost '''
    assert side in ['L', 'R']

    steady = None
    l = 0
    r = len(L)-1
    while l<=r:
        mid = (l+r)//2
        if L[mid] == mid:
            steady = mid
            if side == 'L':
                r = mid-1 #look for smaller indices
            else:
                l = mid+1 #look for larger indices
        elif L[mid] < mid:#go right
            l = mid+1
        else:             #go left
            r = mid-1
    return steady

def cnt_steadies(L):
    mini = find_steady_side(L, 'L')
    maxi = find_steady_side(L, 'R')
    if mini != None:# and maxi!=None:
        return maxi-mini+1
    else:
        return 0

#a recursive solution for (d)- runs in O(log n) time
    
def find_steady_rec(L, l, r, side='L'):
    ''' find L[i]==i or return None, side = 'L' or 'R' for leftmost/rightmost '''
    assert side in ['L', 'R']

    if l > r:
        return None

    steady = None
    mid = (l+r)//2
    if L[mid] == mid:
        steady = mid
        if side == 'L':
           r = mid-1 #look for smaller indices
        else:
           l = mid+1 #look for larger indices
    elif L[mid] < mid:#go right
        l = mid+1
    else:             #go left
        r = mid-1

    result = find_steady_rec(L,  l, r,side)
    
    if steady == None and result == None:
        return None
    if steady == None and result != None:
        return result
    if steady != None and result == None:
        return steady
    
    if side == 'L':
        return min(steady, result)
    return max(steady , result)
    


def cnt_steadies_rec(L):
    mini = find_steady_rec(L,  0, len(L)-1,'L')
    maxi = find_steady_rec(L,  0, len(L)-1,'R')
    if mini != None:
        return maxi-mini+1
    else:
        return 0