import math
# build sparse table, O(n*log(n))
def build_table(A):
    n = len(A)
    mi = [[0 for j in range(int(math.log(n,2)) + 1)] for i in range(n)]
    mx = [[0 for j in range(int(math.log(n,2)) + 1)] for i in range(n)]
    for i in range(n):
        mi[i][0] = i
        mx[i][0] = i
    j = 1
    while 2 ** j <= n:
        i = 0
        while i + 2 ** j - 1 < n:
            if A[mi[i][j - 1]] < A[mi[i + 2 ** (j - 1)][j - 1]]:
                mi[i][j] = mi[i][j-1]
            else:
                mi[i][j] = mi[i + 2 ** (j - 1)][j - 1]
            if A[mx[i][j - 1]] > A[mx[i + 2 ** (j - 1)][j - 1]]:
                mx[i][j] = mx[i][j-1]
            else:
                mx[i][j] = mx[i + 2 ** (j - 1)][j - 1]
            i += 1
        j += 1
    return (mi, mx)
   
# min, max query in range[i, j]. O(1)
def RMQ(A, i, j, mi, mx):
    k = int(math.floor(math.log(j - i + 1, 2)))
    miq = min(A[mi[i][k]], A[mi[j - 2 ** k + 1][k]])
    mxq = max(A[mx[i][k]], A[mx[j - 2 ** k + 1][k]])
    return miq, mxq

# sliding window algorithm. O(n)
def remove_min(A):
    if len(A) <= 1: return 0
    mi, mx = build_table(A)
    i = 0
    j = 0
    max_length = 0
    while j < len(A):
        miq, mxq = RMQ(A, i, j, mi, mx)
        if miq * 2 > mxq:
            max_length = max(max_length, j - i + 1)
            j += 1
        else:
            i += 1
    return len(A) - max_length
    
if __name__ == '__main__':
    print remove_min([4, 5, 100, 9, 10, 11, 12, 15, 200])
    print remove_min([4, 7, 5, 6])
    print remove_min([20, 7, 5, 6])
    print remove_min([20, 4, 1, 3])
    print remove_min([4, 5, 100, 9, 10, 11, 12, 15, 101,102,103,104,105,106,107,108,109,110,111,112])