def bisection_search(input_lines, elemtype1, numel, global_first_elem_idx):
    """
    Returns the 0-indexed first index where the element type changes
    """
    
    if numel == 1:
        return global_first_elem_idx

    half_idx = numel//2
    etype = int(input_lines[half_idx - 1].split()[1])   # 0-indexed
    
    if etype == elemtype1:
        global_first_elem_idx += half_idx
        return bisection_search(input_lines[half_idx:], elemtype1, numel-half_idx, global_first_elem_idx)
    elif etype != elemtype1:
        return bisection_search(input_lines[:half_idx], elemtype1, half_idx, global_first_elem_idx)