You are given a sequence $a_1, a_2, \dots, a_n$ consisting of $n$ non-zero integers (i.e. $a_i \ne 0$). 

You have to calculate two following values:  the number of pairs of indices $(l, r)$ $(l \le r)$ such that $a_l \cdot a_{l + 1} \dots a_{r - 1} \cdot a_r$ is negative;  the number of pairs of indices $(l, r)$ $(l \le r)$ such that $a_l \cdot a_{l + 1} \dots a_{r - 1} \cdot a_r$ is positive; 


-----Input-----

The first line contains one integer $n$ $(1 \le n \le 2 \cdot 10^{5})$ — the number of elements in the sequence.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ $(-10^{9} \le a_i \le 10^{9}; a_i \neq 0)$ — the elements of the sequence.


-----Output-----

Print two integers — the number of subsegments with negative product and the number of subsegments with positive product, respectively.


-----Examples-----
Input
5
5 -3 3 -1 1

Output
8 7

Input
10
4 2 -4 3 1 2 -4 3 2 3

Output
28 27

Input
5
-1 -2 -3 -4 -5

Output
9 6

Difficulty: interview

Starter code:

Solutions:
def main():
    import sys
    input = sys.stdin.readline
    
    n = int(input())
    arr = list(map(int, input().split()))
    
    cnt = [1, 0]
    
    lst = [0] * (n + 1)
    lst[0] = 0
    for i in range(n):
        lst[i + 1] = lst[i] ^ (arr[i] < 0)
        cnt[lst[i + 1]] += 1
    
    ans1 = cnt[0] * cnt[1]
    ans2 = cnt[0] * (cnt[0] - 1) // 2 + cnt[1] * (cnt[1] - 1) // 2
    print(ans1, ans2)
    
    return 0

main()


n=int(input())
l1=list(map(int,input().split()))
negative=0
total=n*(n+1)//2
negative_till=0
positive_till=0
for item in l1:
    if item>0:
        positive_till+=1
    else :
        temp=positive_till
        positive_till=negative_till
        negative_till=temp+1
    negative+=negative_till
print(negative,total-negative)


n = int(input())
a = list(map(int,input().split()))

n = 0
p = 0

cn = 0
cp = 0

for i in a:
    if i < 0:
        cn, cp = cp, cn;
        cn += 1
    else:
        cp += 1
    n += cn
    p += cp
print(n,p)


n = int(input())
a = list([1 if int(x) > 0 else -1 for x in input().split()])
last, pr = 0, 1
for q in a:
    pr *= q
    if pr > 0:
        last += 1
ans = last
for q in range(1, len(a)):
    if a[q-1] > 0:
        last -= 1
    else:
        last = n-q-last
    ans += last
print(n*(n+1)//2-ans, ans)


n = int(input())
a = list(map(int, input().split()))

ans_pos = 0
ans_neg = 0
tmp_pos = 0
tmp_neg = 0
for i in range(n)[::-1]:
    prev_pos = tmp_pos
    prev_neg = tmp_neg
    tmp_pos = 0
    tmp_neg = 0
    if a[i] > 0:
        tmp_pos += 1
        tmp_pos += prev_pos
        tmp_neg += prev_neg
    else:
        tmp_neg += 1
        tmp_pos += prev_neg
        tmp_neg += prev_pos
    ans_pos += tmp_pos
    ans_neg += tmp_neg
print(ans_neg, ans_pos)



from itertools import accumulate
from operator import xor
n = int(input())
l = accumulate([1 if x < 0 else 0 for x in map(int, input().split())], xor)
a = b = 0
cnt = [1, 0]
for e in l:
    a += cnt[e ^ 1]
    b += cnt[e]
    cnt[e] += 1
print(a, b)


a = int(input())
l = list(map(int, input().strip().split()))
neg = [0]
pos = [0]
for i in l:
    t = neg[-1]
    v = pos[-1]
    if i < 0:
        pos.append(t)
        neg.append(v+1)
    else:
        pos.append(v+1)
        neg.append(t)
n = 0
p = 0
for i in range(len(pos)):
    n += neg[i]
    p += pos[i]
print(n,p)

import sys

n = int(sys.stdin.readline().strip())
a = list(map(int,sys.stdin.readline().strip().split()))

v1 = 0
v2 = 0

p = 0
m = 0
for i in range (0, n):
    if a[i] == 0:
        p = 0
        m = 0
    if a[i] > 0:
        p = p + 1
    if a[i] < 0:
        p, m = m, p
        m = m + 1
    v1 = v1 + p
    v2 = v2 + m
print(str(v2) + " " + str(v1))

''' CODED WITH LOVE BY SATYAM KUMAR '''

from sys import stdin, stdout
import heapq
import cProfile, math
from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect, bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
import operator as op
from functools import reduce
import sys

sys.setrecursionlimit(10 ** 6)  # max depth of recursion
threading.stack_size(2 ** 27)  # new thread will get stack of such size
fac_warm_up = False
printHeap = str()
memory_constrained = False
P = 10 ** 9 + 7


class MergeFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.num_sets = n
        self.lista = [[_] for _ in range(n)]

    def find(self, a):
        to_update = []
        while a != self.parent[a]:
            to_update.append(a)
            a = self.parent[a]
        for b in to_update:
            self.parent[b] = a
        return self.parent[a]

    def merge(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.num_sets -= 1
        self.parent[b] = a
        self.size[a] += self.size[b]
        self.lista[a] += self.lista[b]

    def set_size(self, a):
        return self.size[self.find(a)]

    def __len__(self):
        return self.num_sets


def display(string_to_print):
    stdout.write(str(string_to_print) + "\n")


def prime_factors(n):  # n**0.5 complex
    factors = dict()
    for i in range(2, math.ceil(math.sqrt(n)) + 1):
        while n % i == 0:
            if i in factors:
                factors[i] += 1
            else:
                factors[i] = 1
            n = n // i
    if n > 2:
        factors[n] = 1
    return (factors)


def all_factors(n):
    return set(reduce(list.__add__,
                      ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))


def fibonacci_modP(n, MOD):
    if n < 2: return 1
    return (cached_fn(fibonacci_modP, (n + 1) // 2, MOD) * cached_fn(fibonacci_modP, n // 2, MOD) + cached_fn(
        fibonacci_modP, (n - 1) // 2, MOD) * cached_fn(fibonacci_modP, (n - 2) // 2, MOD)) % MOD


def factorial_modP_Wilson(n, p):
    if (p <= n):
        return 0
    res = (p - 1)
    for i in range(n + 1, p):
        res = (res * cached_fn(InverseEuler, i, p)) % p
    return res


def binary(n, digits=20):
    b = bin(n)[2:]
    b = '0' * (digits - len(b)) + b
    return b


def is_prime(n):
    """Returns True if n is prime."""
    if n < 4:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False
    i = 5
    w = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += w
        w = 6 - w
    return True


def generate_primes(n):
    prime = [True for i in range(n + 1)]
    p = 2
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 1
    return prime


factorial_modP = []


def warm_up_fac(MOD):
    nonlocal factorial_modP, fac_warm_up
    if fac_warm_up: return
    factorial_modP = [1 for _ in range(fac_warm_up_size + 1)]
    for i in range(2, fac_warm_up_size):
        factorial_modP[i] = (factorial_modP[i - 1] * i) % MOD
    fac_warm_up = True


def InverseEuler(n, MOD):
    return pow(n, MOD - 2, MOD)


def nCr(n, r, MOD):
    nonlocal fac_warm_up, factorial_modP
    if not fac_warm_up:
        warm_up_fac(MOD)
        fac_warm_up = True
    return (factorial_modP[n] * (
                (pow(factorial_modP[r], MOD - 2, MOD) * pow(factorial_modP[n - r], MOD - 2, MOD)) % MOD)) % MOD


def test_print(*args):
    if testingMode:
        print(args)


def display_list(list1, sep=" "):
    stdout.write(sep.join(map(str, list1)) + "\n")


def display_2D_list(li):
    for i in li:
        print(i)


def prefix_sum(li):
    sm = 0
    res = []
    for i in li:
        sm += i
        res.append(sm)
    return res


def get_int():
    return int(stdin.readline().strip())


def get_tuple():
    return map(int, stdin.readline().split())


def get_list():
    return list(map(int, stdin.readline().split()))


memory = dict()


def clear_cache():
    nonlocal memory
    memory = dict()


def cached_fn(fn, *args):
    nonlocal memory
    if args in memory:
        return memory[args]
    else:
        result = fn(*args)
        memory[args] = result
        return result


def ncr(n, r):
    return math.factorial(n) / (math.factorial(n - r) * math.factorial(r))


def binary_search(i, li):
    fn = lambda x: li[x] - x // i
    x = -1
    b = len(li)
    while b >= 1:
        while b + x < len(li) and fn(b + x) > 0:  # Change this condition 2 to whatever you like
            x += b
        b = b // 2
    return x


# -------------------------------------------------------------- MAIN PROGRAM


TestCases = False
fac_warm_up_size = 10 ** 5 + 100
optimise_for_recursion = False  # Can not be used clubbed with TestCases WHen using recursive functions, use Python 3


def main():
    n = get_int()
    li = get_list()
    dp = [[0,0]]
    posi = 0
    for i in li:
        if i>0:
            dp.append([dp[-1][0]+1, dp[-1][1]])
            posi += dp[-1][0]
        else:
            dp.append([dp[-1][1], dp[-1][0] + 1])
            posi += dp[-1][0]
    #print(dp)
    print((n*(n+1))//2 - posi, posi)

# --------------------------------------------------------------------- END=


if TestCases:
    for i in range(get_int()):
        main()
else:
    main() if not optimise_for_recursion else threading.Thread(target=main).start()

N = int(input())
nums = list(map(int, input().split()))

# (neg, pos)
tot = (1, 0) if nums[0] < 0 else (0, 1)

runTot = tot
for i in range(1, N):
    if nums[i] > 0:
        tot = (tot[0], tot[1] + 1)
    else:
        tot = (tot[1] + 1, tot[0])
    runTot = (runTot[0] + tot[0], runTot[1] + tot[1])

print(runTot[0], runTot[1])


n = int(input())
arr = list(map(int, input().split()))
for i in range(n):
    arr[i] = arr[i] // abs(arr[i])
pref = [1]
for i in range(n):
    pref.append(pref[-1] * arr[i])
plus = minus = 0
res_pl = res_mn = 0
for i in range(n + 1):
    if pref[i] == 1:
        res_pl += plus
        res_mn += minus
        plus += 1
    else:
        res_pl += minus
        res_mn += plus
        minus += 1
print(res_mn, res_pl)


n=int(input())
a=[int(x) for x in input().split()]
pref=[0]
for item in a:
    if item<0:
        pref.append(pref[-1]+1)
    else:
        pref.append(pref[-1])
non=0
on=0
arr=0
for item in pref:
    if item%2==0:
        arr+=non
        on+=1
    else:
        arr+=on
        non+=1
print(arr,n*(n+1)//2-arr)
    


n = int(input())
l = [int(s) for s in input().split()]
dp = [[0,0] for i in range(n)]
if l[0] < 0:
    dp[0][0] = 1
else:
    dp[0][1] = 1
# print(dp)
for i in range(1,n):
    if l[i]<0:
        dp[i][0]=dp[i-1][1]+1
        dp[i][1]=dp[i-1][0]
    else:
        dp[i][0] = dp[i-1][0]
        dp[i][1] = dp[i-1][1]+1
ans1 = sum([i[0] for i in dp])
ans2 = sum([i[1] for i in dp])
print(ans1, ans2)


def solve(a, n):
    neg = [0 for i in range(n)]
    pos = [0 for i in range(n)]
    if a[0] < 0:
        neg[0] = 1
    else:
        pos[0] = 1
    for i in range(1, n):
        if a[i] < 0:
            neg[i] += 1 + pos[i - 1]
            pos[i] += neg[i - 1]
        else:
            pos[i] += 1 + pos[i - 1]
            neg[i] += neg[i - 1]
    totalNeg = 0
    totalPos = 0
    
    for i in range(n):
        totalNeg += neg[i]
        totalPos += pos[i]
        
    return totalNeg, totalPos

n = int(input())
a = list(map(int, input().split()))
        
l, r = solve(a, n)

print(str(l) +' '+str(r))

import sys 
from collections import defaultdict
input = lambda : sys.stdin.readline().rstrip()

n = int(input())
arr = list(map(int, input().split()))
ans = [0, 0]
dp = [0, 0]
for i in arr:
  if i > 0:
    a = dp[0] + 1
    b = dp[1]
  else:
    a = dp[1]
    b = dp[0] + 1
  dp = [a, b]
  ans[0] += a 
  ans[1] += b 
  #print(dp)

print(*ans[::-1])



n=int(input())
arr=list([int(x)>0 for x in input().split()])

pos = neg = lastpos = lastneg = curpos = curneg = 0
for i in range(n):
    if arr[i]:
        curpos = 1+lastpos
        curneg = lastneg
    else:
        curpos = lastneg
        curneg = 1+lastpos
    pos += curpos
    neg += curneg
    lastpos = curpos
    lastneg = curneg

print(neg,pos)


from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 10**5+10
MOD = 10**9+7
def isprime(n):
    n = abs(int(n))
    if n < 2:
        return False
    if n == 2: 
        return True    
    if not n & 1: 
        return False
    for x in range(3, int(n**0.5) + 1, 2):
        if n % x == 0:
            return False
    return True

def mhd(a,b):
    return abs(a[0]-b[0])+abs(b[1]-a[1])

def charIN(x= ' '):
    return(sys.stdin.readline().strip().split(x))

def arrIN(x = ' '):
    return list(map(int,sys.stdin.readline().strip().split(x)))

def eld(x,y):
    a = y[0]-x[0]
    b = x[1]-y[1]
    return (a*a+b*b)**0.5

def lgcd(a):
    g = a[0]
    for i in range(1,len(a)):
        g = math.gcd(g,a[i])
    return g

def ms(a):
    msf = -MAX
    meh = 0
    st = en = be = 0
    for i in range(len(a)):
        meh+=a[i]
        if msf<meh:
            msf = meh
            st = be
            en = i
        if meh<0:
            meh = 0
            be = i+1
    return msf,st,en

def ncr(n,r):
    num=den=1
    for i in range(r):
        num = (num*(n-i))%MOD
        den = (den*(i+1))%MOD

    return (num*(pow(den,MOD-2,MOD)))%MOD



def flush():
    return sys.stdout.flush()


def fac(n):
    ans = 1
    for i in range(1,n+1):
        ans*=i
        ans%=MOD
    return ans

'''*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*'''
def fun(a,n,m):
    x = [0]*n
    ans = 0
    mp = dict()
    x[0]=a[0]
    for i in range(1,n):
        x[i] = x[i-1]^a[i]
    for i in range(n):
        tmp = m^x[i]
        if tmp in list(mp.keys()):
            ans+=mp[tmp]
        if x[i]==m:
            ans+=1
        mp[x[i]] = mp.get(x[i],0)+1
    return ans

n = int(input())
a = arrIN()
x = []
for i in a:
    if i>0:
        x.append(1)
    else:
        x.append(-1)
ans = fun(x,n,-1)+fun(x,n,-2)
print(ans,(n*(n+1))//2-ans)





def ii(): return int(input())
def si(): return input()
def mi(): return map(int,input().split())
def li(): return list(mi())

import math

n=ii()
a=li()
l=[0]*200005
s=ans=0
t=(n*(n+1))//2
for i in range(n):
    if a[i]<0:
        l[i]=1 
    c,d=1,0 
for i in range(n):
    s+=l[i]
    if s%2!=0:
        ans+=d 
        d+=1 
    else:
        ans+=c 
        c+=1
print(t-ans,ans)

I = lambda : int(input())

sign = lambda x: -1 if(x<0) else 1

LI = lambda : [sign(int(x)) for x in input().split()]
c = lambda x: x*(x-1)//2

n = I()
a = LI()
for i in range(1,len(a)):
	a[i]*=a[i-1]

p = 0
i = 0
for x in a:
	if(x==-1): i+=1
	else: p+=1

print(c(n)+n-(c(p)+c(i)+p),c(p)+c(i)+p)


n = int(input())
a = list(map(int, input().split()))

left = [0]*n
for i, el in enumerate(a):
    if i == 0:
        left[i] = int(el < 0)
    else:
        left[i] = left[i-1] + int(el < 0)

l_count = [0]*n
for i, el in enumerate(left):
    if i == 0:
        l_count[i] = 1
    else:
        l_count[i] = l_count[i-1] + int(left[i-1]%2 == 0)

neg_count = 0
for r in range(n):
    if left[r]%2 == 1:
        neg_count += l_count[r]
    else:
        neg_count += r+1 - l_count[r]

pos_count = n*(n+1)//2 - neg_count

print(neg_count, pos_count)

n = int(input())
arr = [int(s) for s in input().split()]
ans = [0, 0]
last = [0, 0]
now = 0
for i in arr:
    if i < 0:
        now = 1 if now == 0 else 0
    last[now] += 1
ans[0] += last[0]
ans[1] += last[1]
# print(last)
for i in range(1, n):
    if arr[i - 1] < 0:
        last[0], last[1] = last[1], last[0]
    last[0] -= 1
    ans[0] += last[0]
    ans[1] += last[1]
    # print(last)
print(ans[1], ans[0])

n = int(input())
a = list(map(int, input().split()))
cnt_plus, cnt_minus = 0, 0
cur_plus, cur_minus = 0, 0
for v in a:
	if v > 0:
		cur_plus += 1
	else:
		cur_minus, cur_plus = cur_plus + 1, cur_minus		
	cnt_plus += cur_plus
	cnt_minus += cur_minus
print(cnt_minus, cnt_plus)


import sys
sin = sys.stdin

sin.readline()
arr = sin.readline().split()
arr = [int(i) for i in arr]

lp = ln = ep = en = 0

for i in arr:
    newNeg = 0
    newPos = 0
    if i < 0:
        newNeg = ep + 1
        newPos = en
    if i > 0:
        newNeg = en
        newPos = ep + 1
    lp += ep
    ln += en
    ep = newPos
    en = newNeg

print(ln + en, lp + ep)



N = int(input())

d = 1
pl = 0
mn = 0
apl = 0
amn = 0
for k in map(int,input().split()):
    if k < 0: d = d * (-1)

    if d < 0:
        apl += mn
        amn += pl
    else:
        apl += pl
        amn += mn

    if d < 0:
        mn += 1
        amn += 1
    else:
        pl += 1
        apl += 1

print(amn, apl)