def solution(A):
    uppersum = sum(A)
    lowersum = 0
    term = 0
    for i, x in enumerate(A):        
        lowersum += term
        term = x
        uppersum -= term
        if lowersum == uppersum:
            return i
    return -1

from bisect import bisect_right

def solution(A):
    n = len(A)
    upper = sorted([i + x for i, x in enumerate(A)])
    lower = sorted([i - x for i, x in enumerate(A)])
    counter = 0
    for v in upper:
        counter += bisect_right(lower, v)
    counter -= n * (n + 1) / 2
    if counter > 1e7:
        return -1
    return counter    

def solution(A):
    checked = {}
    r = 0
    for i, x in enumerate(A):
        if not x in checked:
            checked[x] = True
            r = i
    return r

def solution(N):
    zeros = bin(N)[2:].split('1')
    zeros = zeros[:-1] # Just in case there are trailing zeros
    return max(map(len, zeros))

# This one is silly:
def solution(X, Y, D):
    distance = Y - X
    if distance % D == 0:
        return (Y - X) / D
    else:
        return ((Y - X) / D) + 1 # Abussing Python's broken division.

def solution(A):
    A = sorted(A) # The complexity is O(N log(N)), unfortunately. But Codility wasn't able to tell. 
    for i in range(len(A)):
        if A[i] != i + 1:
            return i + 1
    return len(A) + 1

def solution(A):
    n = len(A)
    check = {i+1:False for i in xrange(n)}
    for x in A:
        if x not in check:
            return 0
        else:
            if check[x] == True:
                return 0
            else:
                check[x] = True
    for x in check:
        if check[x] == False:
            return 0
    return 1

# Minimal solution 
# A detailed version would require ordering the array 
# and run over it while counting the times the value changes.
# (Which I guess is more or less the way Python turns a list into a set.)
def solution(A):
    return len(set(A))

def solution(S):
    stack = 0
    for x in S:
        if x == '(':
            stack += 1
        if x == ')':
            stack -= 1
        if stack < 0:
            return 0
    if stack == 0:
        return 1
    else:
        return 0

# First time I got 100% with my first submit.
def solution(A, B):
    fish_downstream = []
    up_survivors = 0
    for i, direction in enumerate(B):
        if direction == 1:
            fish_downstream.append(A[i])
        else: 
            is_active = 1
            up = A[i]
            while is_active:
                if len(fish_downstream) != 0:
                    down = fish_downstream.pop()
                    if down > up:
                        fish_downstream.append(down)
                        is_active = 0
                else:
                    is_active = 0
                    up_survivors += 1
    return len(fish_downstream) + up_survivors

def count_down(n, dicc):
    for m in [1,2]:
        if n-m in dicc:
            dicc[n] = dicc.get(n,0)+dicc[n-m] 
    return dicc

def climbing_ways_counter(L):
    dicc = {0:1}
    for n in xrange(L):
        count_down(n,dicc)
    return dicc

def solution(A, B):
    L = len(A) + 1
    # Weird optimization trick. Modulo operation is too slow...
    # Had to look up online for it:
    B = [(1<<b)-1 for b in B] 
    d = climbing_ways_counter(L)
    return [d[a] & b for a,b in zip(A,B)]