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

You have to calculate two following values:

  1. the number of pairs of indices (l, r) (l ≤ r) such that a_l ⋅ a_{l + 1} ... a_{r - 1} ⋅ a_r is negative; 
  2. the number of pairs of indices (l, r) (l ≤ r) such that a_l ⋅ a_{l + 1} ... a_{r - 1} ⋅ a_r is positive; 

Input

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

The second line contains n integers a_1, a_2, ..., a_n (-10^{9} ≤ a_i ≤ 10^{9}; a_i ≠ 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
import sys, os, io
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s + '\n')
def wi(n): sys.stdout.write(str(n) + '\n')
def wia(a): sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math,datetime,functools,itertools,operator,bisect
from collections import deque,defaultdict,OrderedDict

N = 1000001
p=10**9+7
fact = [None] * (N + 1) 
fact[0] = 1 
for i in range(1, N + 1): 
    fact[i] = (fact[i - 1] * i) % p 
def main():
    starttime=datetime.datetime.now()
    if(os.path.exists('input.txt')):
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")

    for _ in range(1):
        n=ri()
        a=ria()
        ans=0
        cup=0
        prev=0
        c=0
        em=0
        om=0
        tot=(n*(n+1))//2
        for i in range(n):
            if a[i]<0:
                c+=1
                z=ans
                if c%2==0:
                    ans+=i+1-prev+em
                    em+=i+1-prev
                else:
                    ans+=i+1-prev+om
                    om+=i+1-prev
                cup=ans-z
                prev=i+1
            else:
                ans+=cup
        print(ans,tot-ans)
        
                
            
                
                
                
        
            
        
        
                    
            
            
        
        
        
        
        
            
                
                
            
            
            
            
        


                
            
            

                    
        
        
                
        
        
                
                    
        
        
        
        
        
        
        
       
  
            
            

            
                
                
        
        
            
                    
            
            

        
        

    
                
                    
                
                
                
                    
                
        
        
        
        
        
        
        
            
            
        
        
        
            
        
                
        
        
            
            
        
        
                    
                    
        
        

                
                    
        
            
            
                
        
        
           
            
            
            

        
        
        


            
            
            
           
            
            
            
            
        
            
                
            
            
                            
                
            
            
        
            
            
            
            
            
            
        
        
                
                
                
                  
                    
                    
                
            
        
        
                
                
            
        
        
                    
                    
                    
            
            
            
            
            
        

                    
                    
          
        
        
        
            
            
                
                    
            
        
        
                
                    
                    
                    
            

        
            
            

            

                
                
                
                
            
        

        
        
            
            
                
                
        
        
        
                
            
        
        
        
        
        
            
            
        
                
                
                

        

                    
                
            

        
        
            
            
            
                
                
            
                
                
        

                
        
        

        
            
                
                
            
        
            
            
                
                

    

            
        
        
       
                
                    
                
            
            
        

            
            
                
            
            
        
                
        
                
                
            
        
            
                
                
                    
                
                
        
        


        
        
        
        

            
                    
            
                    
        
 

                
        
        

            
        
        
                
            
                
     
        
        
                
                
        
        
        
        
                
        

            
                
            


        
                
            
            
            
            
                    
        















    #<--Solving Area Ends
    endtime=datetime.datetime.now()
    time=(endtime-starttime).total_seconds()*1000
    if(os.path.exists('input.txt')):
        print("Time:",time,"ms")  
    
                
class FastReader(io.IOBase):
    newlines = 0

    def __init__(self, fd, chunk_size=1024 * 8):
        self._fd = fd
        self._chunk_size = chunk_size
        self.buffer = io.BytesIO()

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self, size=-1):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()


class FastWriter(io.IOBase):

    def __init__(self, fd):
        self._fd = fd
        self.buffer = io.BytesIO()
        self.write = self.buffer.write

    def flush(self):
        os.write(self._fd, self.buffer.getvalue())
        self.buffer.truncate(0), self.buffer.seek(0)


class FastStdin(io.IOBase):
    def __init__(self, fd=0):
        self.buffer = FastReader(fd)
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


class FastStdout(io.IOBase):
    def __init__(self, fd=1):
        self.buffer = FastWriter(fd)
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.flush = self.buffer.flush


if __name__ == '__main__':
    sys.stdin = FastStdin()
    sys.stdout = FastStdout()
    main()







