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