def n_smaller(num,a,i1,i2):
    """
    Returns the number of elements smaller
    than num in sorted array, a between indices 
    i1 and i2
    """
    if num>a[i2-1]:
        return i2-i1+1
    elif num<a[i1-1]:
        return 0
    hi=i2-1; lo=i1-1
    mid = int((lo+hi)/2)
    while hi>lo:
        if num==a[mid] or hi-lo<=1:
            return mid+1-i1+1
        elif num>a[mid]:
            lo=mid
        else:
            hi=mid
        mid = int((lo+hi)/2)
    return lo+1-i1+1