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])

aW1wb3J0IG1hdGgKIyBidWlsZCBzcGFyc2UgdGFibGUsIE8obipsb2cobikpCmRlZiBidWlsZF90YWJsZShBKToKICAgIG4gPSBsZW4oQSkKICAgIG1pID0gW1swIGZvciBqIGluIHJhbmdlKGludChtYXRoLmxvZyhuLDIpKSArIDEpXSBmb3IgaSBpbiByYW5nZShuKV0KICAgIG14ID0gW1swIGZvciBqIGluIHJhbmdlKGludChtYXRoLmxvZyhuLDIpKSArIDEpXSBmb3IgaSBpbiByYW5nZShuKV0KICAgIGZvciBpIGluIHJhbmdlKG4pOgogICAgICAgIG1pW2ldWzBdID0gaQogICAgICAgIG14W2ldWzBdID0gaQogICAgaiA9IDEKICAgIHdoaWxlIDIgKiogaiA8PSBuOgogICAgICAgIGkgPSAwCiAgICAgICAgd2hpbGUgaSArIDIgKiogaiAtIDEgPCBuOgogICAgICAgICAgICBpZiBBW21pW2ldW2ogLSAxXV0gPCBBW21pW2kgKyAyICoqIChqIC0gMSldW2ogLSAxXV06CiAgICAgICAgICAgICAgICBtaVtpXVtqXSA9IG1pW2ldW2otMV0KICAgICAgICAgICAgZWxzZToKICAgICAgICAgICAgICAgIG1pW2ldW2pdID0gbWlbaSArIDIgKiogKGogLSAxKV1baiAtIDFdCiAgICAgICAgICAgIGlmIEFbbXhbaV1baiAtIDFdXSA+IEFbbXhbaSArIDIgKiogKGogLSAxKV1baiAtIDFdXToKICAgICAgICAgICAgICAgIG14W2ldW2pdID0gbXhbaV1bai0xXQogICAgICAgICAgICBlbHNlOgogICAgICAgICAgICAgICAgbXhbaV1bal0gPSBteFtpICsgMiAqKiAoaiAtIDEpXVtqIC0gMV0KICAgICAgICAgICAgaSArPSAxCiAgICAgICAgaiArPSAxCiAgICByZXR1cm4gKG1pLCBteCkKICAgCiMgbWluLCBtYXggcXVlcnkgaW4gcmFuZ2VbaSwgal0uIE8oMSkKZGVmIFJNUShBLCBpLCBqLCBtaSwgbXgpOgogICAgayA9IGludChtYXRoLmZsb29yKG1hdGgubG9nKGogLSBpICsgMSwgMikpKQogICAgbWlxID0gbWluKEFbbWlbaV1ba11dLCBBW21pW2ogLSAyICoqIGsgKyAxXVtrXV0pCiAgICBteHEgPSBtYXgoQVtteFtpXVtrXV0sIEFbbXhbaiAtIDIgKiogayArIDFdW2tdXSkKICAgIHJldHVybiBtaXEsIG14cQoKIyBzbGlkaW5nIHdpbmRvdyBhbGdvcml0aG0uIE8obikKZGVmIHJlbW92ZV9taW4oQSk6CiAgICBpZiBsZW4oQSkgPD0gMTogcmV0dXJuIDAKICAgIG1pLCBteCA9IGJ1aWxkX3RhYmxlKEEpCiAgICBpID0gMAogICAgaiA9IDAKICAgIG1heF9sZW5ndGggPSAwCiAgICB3aGlsZSBqIDwgbGVuKEEpOgogICAgICAgIG1pcSwgbXhxID0gUk1RKEEsIGksIGosIG1pLCBteCkKICAgICAgICBpZiBtaXEgKiAyID4gbXhxOgogICAgICAgICAgICBtYXhfbGVuZ3RoID0gbWF4KG1heF9sZW5ndGgsIGogLSBpICsgMSkKICAgICAgICAgICAgaiArPSAxCiAgICAgICAgZWxzZToKICAgICAgICAgICAgaSArPSAxCiAgICByZXR1cm4gbGVuKEEpIC0gbWF4X2xlbmd0aAogICAgCmlmIF9fbmFtZV9fID09ICdfX21haW5fXyc6CiAgICBwcmludCByZW1vdmVfbWluKFs0LCA1LCAxMDAsIDksIDEwLCAxMSwgMTIsIDE1LCAyMDBdKQogICAgcHJpbnQgcmVtb3ZlX21pbihbNCwgNywgNSwgNl0pCiAgICBwcmludCByZW1vdmVfbWluKFsyMCwgNywgNSwgNl0pCiAgICBwcmludCByZW1vdmVfbWluKFsyMCwgNCwgMSwgM10pCiAgICBwcmludCByZW1vdmVfbWluKFs0LCA1LCAxMDAsIDksIDEwLCAxMSwgMTIsIDE1LCAxMDEsMTAyLDEwMywxMDQsMTA1LDEwNiwxMDcsMTA4LDEwOSwxMTAsMTExLDExMl0p