import random
import time
 
#http://c...content-available-to-author-only...e.com/recipes/577944-random-binary-list/
randBinList = lambda n: [random.randint(0,1) for b in range(1,n+1)]
 
def f(A):
  a, b = 0, 0
  for i in xrange(len(A)):
    m = i & 1 ^ A[i]
    a, b = m + a, (not m) + b
  return min(a, b)
 
def minFlipMarkMeyer(a):
    return min(
        sum(n == i % 2 for i, n in enumerate(a)),
        sum(n == (i + 1) % 2 for i, n in enumerate(a))
    )
 
def minFlipTrincot1(a):
    flips = sum((n ^ i) & 1 for i, n in enumerate(a))
    return min(flips, len(a)-flips)
 
def minFlipTrincot2(a):
    return (len(a)-abs(sum(-1 if (n^i)&1 else 1 for i,n in enumerate(a)))) // 2
 
A = randBinList(10000000)
 
start = time.time()
print f(A)
end = time.time()
print(end - start)
 
start = time.time()
print "%s (minFlipMarkMeyer)" % minFlipMarkMeyer(A)
end = time.time()
print(end - start)
 
start = time.time()
print "%s (minFlipTrincot1)" % minFlipTrincot1(A)
end = time.time()
print(end - start)
 
start = time.time()
print "%s (minFlipTrincot2)" % minFlipTrincot2(A)
end = time.time()
print(end - start)

aW1wb3J0IHJhbmRvbQppbXBvcnQgdGltZQoKI2h0dHA6Ly9jLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5lLmNvbS9yZWNpcGVzLzU3Nzk0NC1yYW5kb20tYmluYXJ5LWxpc3QvCnJhbmRCaW5MaXN0ID0gbGFtYmRhIG46IFtyYW5kb20ucmFuZGludCgwLDEpIGZvciBiIGluIHJhbmdlKDEsbisxKV0KCmRlZiBmKEEpOgogIGEsIGIgPSAwLCAwCiAgZm9yIGkgaW4geHJhbmdlKGxlbihBKSk6CiAgICBtID0gaSAmIDEgXiBBW2ldCiAgICBhLCBiID0gbSArIGEsIChub3QgbSkgKyBiCiAgcmV0dXJuIG1pbihhLCBiKQoKZGVmIG1pbkZsaXBNYXJrTWV5ZXIoYSk6CiAgICByZXR1cm4gbWluKAogICAgICAgIHN1bShuID09IGkgJSAyIGZvciBpLCBuIGluIGVudW1lcmF0ZShhKSksCiAgICAgICAgc3VtKG4gPT0gKGkgKyAxKSAlIDIgZm9yIGksIG4gaW4gZW51bWVyYXRlKGEpKQogICAgKQoKZGVmIG1pbkZsaXBUcmluY290MShhKToKICAgIGZsaXBzID0gc3VtKChuIF4gaSkgJiAxIGZvciBpLCBuIGluIGVudW1lcmF0ZShhKSkKICAgIHJldHVybiBtaW4oZmxpcHMsIGxlbihhKS1mbGlwcykKCmRlZiBtaW5GbGlwVHJpbmNvdDIoYSk6CiAgICByZXR1cm4gKGxlbihhKS1hYnMoc3VtKC0xIGlmIChuXmkpJjEgZWxzZSAxIGZvciBpLG4gaW4gZW51bWVyYXRlKGEpKSkpIC8vIDIKCkEgPSByYW5kQmluTGlzdCgxMDAwMDAwMCkKCnN0YXJ0ID0gdGltZS50aW1lKCkKcHJpbnQgZihBKQplbmQgPSB0aW1lLnRpbWUoKQpwcmludChlbmQgLSBzdGFydCkKCnN0YXJ0ID0gdGltZS50aW1lKCkKcHJpbnQgIiVzIChtaW5GbGlwTWFya01leWVyKSIgJSBtaW5GbGlwTWFya01leWVyKEEpCmVuZCA9IHRpbWUudGltZSgpCnByaW50KGVuZCAtIHN0YXJ0KQoKc3RhcnQgPSB0aW1lLnRpbWUoKQpwcmludCAiJXMgKG1pbkZsaXBUcmluY290MSkiICUgbWluRmxpcFRyaW5jb3QxKEEpCmVuZCA9IHRpbWUudGltZSgpCnByaW50KGVuZCAtIHN0YXJ0KQoKc3RhcnQgPSB0aW1lLnRpbWUoKQpwcmludCAiJXMgKG1pbkZsaXBUcmluY290MikiICUgbWluRmxpcFRyaW5jb3QyKEEpCmVuZCA9IHRpbWUudGltZSgpCnByaW50KGVuZCAtIHN0YXJ0KQ==