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 java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        solve(in, out);
        out.close();
    }

    static String reverse(String s){
        return (new StringBuilder(s)).reverse().toString();
    }

    static void sort(int ar[]){
        int n=ar.length;
        ArrayList<Integer> a=new ArrayList<>();
        for(int i=0;i<n;i++)
            a.add(ar[i]);
        Collections.sort(a);
        for(int i=0;i<n;i++)
            ar[i]=a.get(i);
    }

    static long ncr(long n,long r, long mod){
        if(r==0)
            return 1;
        long val=ncr(n-1,r-1,mod);
        val=(n*val)%mod;
        val=(val*modInverse(r,mod))%mod;
        return val;
    }

    public static void solve(InputReader sc, PrintWriter pw) {
        int i,j=0;
        int t=1;
        // int t=sc.nextInt();
        u:while(t-->0){
            int n=sc.nextInt();
            int a[]=new int[n];
            int y[]=new int[n];
            int z[]=new int[n];
            for(i=0;i<n;i++){
                a[i]=sc.nextInt();
            }
            if(a[0]>0){
                y[0]=1;
            }
            else
                z[0]=1;
            for(i=1;i<n;i++){
                if(a[i]>0){
                    y[i]=y[i-1]+1;
                    z[i]=z[i-1];
                }
                else{
                    y[i]=z[i-1];
                    z[i]=y[i-1]+1;
                }
            }
            long sum1=0,sum2=0;
            for(i=0;i<n;i++){
                sum1+=y[i];
                sum2+=z[i];
            }
            pw.println(sum2+" "+sum1);
        }
    }
    static class Pair implements Comparable<Pair>{
        int a;
        int b;
        // int i;
        Pair(int a,int b){
            this.a=a;
            this.b=b;
            // this.i=i;
        }   
        public int compareTo(Pair p){
            if(a!=p.a)
                return (a-p.a);
            return (b-p.b);
        }
    }
 
    static boolean isPrime(int n) { 
        if (n <= 1) 
            return false; 
        if (n <= 3) 
            return true; 
        if (n % 2 == 0 || n % 3 == 0) 
            return false; 
        for (int i = 5; i * i <= n; i = i + 6) 
            if (n % i == 0 || n % (i + 2) == 0) 
                return false; 
        return true; 
    } 
    static int gcd(int a, int b) { 
        if (b == 0) 
            return a; 
        return gcd(b, a % b);  
    } 
    static long fast_pow(long base,long n,long M){
        if(n==0)
           return 1;
        if(n==1)
            return base%M;
        long halfn=fast_pow(base,n/2,M);
        if(n%2==0)
            return ( halfn * halfn ) % M;
        else
            return ( ( ( halfn * halfn ) % M ) * base ) % M;
    }
    static long modInverse(long n,long M){
        return fast_pow(n,M-2,M);
    }
 
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
 
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
 
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
    }
}