import random

def random_array(n):
    """Return an array of length n whose entries are random in {-n,...,n}"""
    return [random.randrange(-n, n) for i in range(n)]

def fib0(n):
    """Return 1 if n == 0 or 2*fib0(n-1) if n > 0"""
    return 2**n

def fib3(n):
    """Return a Fibonnaci-like number"""
    if n <= 2: return 1
    # we'll set this up so that a[i] = fib3(i)
    a = (n+1)*[None]
    a[0:3] = [1, 1, 1]
    for i in range(3,n+1):
        a[i] = a[i-1] + a[i-2] + a[i-3]
    return a[n]

def largest_two(a):
    """Return the sum of the largest two values in a"""
    if len(a) < 2: raise ValueError('a must have length at least 2')
    maxi = 0
    for i in range(1,len(a)):
        if a[i] > a[maxi]: maxi = i
    maxj = -1
    for j in range(len(a)):
        if j != maxi and (maxj < 0 or a[j] > a[maxj]): maxj = j
    return a[maxj] + a[maxi]

def smallest_half(a):
    """Return the sum of the smallest len(a)//2 values in a"""
    a_copy = a[:]
    a_copy.sort()
    return reduce(lambda x,y : x+y, a_copy[0:len(a)//2])

def median(a):
    """Return the element of rank len(a)//2 in a"""
    a_copy = a[:]
    a_copy.sort()
    return a_copy[len(a)//2]

def majority(a):
    """Return the majority element in a or None if no majority exists"""
    med = median(a)
    if a.count(med) > len(a)//2: return med
    return None

def split(a, x):
    """Split a into three arrays around x"""
    (a1, a2, a3) = ([], [], [])
    for y in a:
        if y < x: a1.append(y)
        elif y == x: a2.append(y)
        else: a3.append(y)
    return (a1, a2, a3)

def inversions0(a):
    """Count the number of pairs (i,j) such that i<j and a[i] > a[j]"""
    # a slow implementation - just to check correctness
    count = 0
    for i in range(len(a)):
        for j in range(i+1, len(a)):
            if a[i] > a[j]: count += 1
    return count
 
def inversions(a):
    """Count the number of pairs (i,j) such that i<j and a[i] > a[j]"""
    # sort a but keep track of the original index of each element
    b = [(a[i],i) for i in range(len(a))]
    b.sort()
    # check how far each element moved from its original index
    d = [ abs(b[i][1]-i) for i in range(len(b))]
    return sum(d) // 2 # divide by 2 since we counted (i,j) and (j,i)
        
def convolve(a, b):
    """Compute the convolution of a and b"""
    c = []
    for i in range(len(a)-len(b)):
        c.append(0)
        for j in range(len(b)):
            c[i] += a[i+j]*b[j]
    return c

def find_max(a):
    """Return the index of the maximum value in a"""
    imax = 0
    for i in range(1, len(a)):
        if a[i] > a[imax]: imax = i
    return imax

def bentley0(a):
    """Return the indices (i,j) such that a[i]+...+a[j] is maximized"""
    # slow implementation, just for testing
    (imax, jmax) = (1, 0)
    for i in range(len(a)):
        for j in range(i, len(a)+1):
            if sum(a[i:j]) > sum(a[imax:jmax]):
                (imax, jmax) = (i, j)
    return (imax, jmax)

def bentley(a):
    """Return the indices (i,j) such that a[i]+...+a[j-1] is maximized"""
    # b[j] = i such that a[i]+...+a[j] is maximum over all i
    b = len(a)*[None]
    # bval[j] = a[i]+...+a[j] that is maximum over all i
    bval = len(a)*[None]
    if a[0] < 0:
        # a[0] is negative, so it should never be included in any answer
        b[0] = 1
        bval[0] = 0
    else:
        # a[0] is positive, so it might be included in some answers
        b[0] = 0
        bval[0] = a[0]
    for j in range(1, len(a)):
        if bval[j-1] + a[j] > 0:
            # better to grow a[i]+...+a[j]
            b[j] = b[j-1]
            bval[j] = bval[j-1] + a[j]
        else: 
            # better to restart at 0, since a[i]+...+a[j] is negative
            b[j] = j+1
            bval[j] = 0
    j = find_max(bval)
    i = b[j]
    return (i,j+1)