Phone-pe Interview SDE 1

import sys

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
        
    n = int(input_data[0])
    a = [int(x) for x in input_data[1:n+1]]
    
    p = [0] * n
    curr = 0
    re = 0
    ro = 0
    
    for i in range(n):
        curr ^= (a[i] & 1)
        p[i] = curr
        if curr == 0:
            re += 1
        else:
            ro += 1
            
    ans = 0
    le = 1
    lo = 0
    
    for i in range(n):
        if p[i] == 0:
            ans += le
            le += 1
        else:
            ans += lo
            lo += 1
            
    le = 1
    lo = 0
    max_diff = 0
    
    for i in range(n):
        diff = (le * ro + lo * re) - (le * re + lo * ro)
        if diff > max_diff:
            max_diff = diff
            
        if p[i] == 0:
            re -= 1
            le += 1
        else:
            ro -= 1
            lo += 1
            
    print(ans + max_diff)

if __name__ == '__main__':
    solve()