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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

//import Number_theory.pair;

public class hacker49 {
	public static int r1=0;
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
	static class pair{
		private long cnt;
		private long[] fq;
		private long[] pref;
		pair(){
			fq=new long[41];
			pref=new long[41];
			cnt=(long)0;
		}	
	}
	
	public static void main(String[] args) {
		OutputStream outputStream =System.out;
	    PrintWriter out =new PrintWriter(outputStream);
		FastReader s=new FastReader();
    	int n=s.nextInt();
    	int neg=0;
    	int pos=0;
    	long[] a=new long[n];
    	for(int i=0;i<n;i++) {
    		a[i]=s.nextLong();
    		if(a[i]<(long)0) {
    			neg++;
    		}else {
    			pos++;
    		}
    	}
    	long[] f1=new long[neg+1];
    	long[] f2=new long[pos+1];
    	long[] f3=new long[neg+1];
    	int i=1;
    	int j=1;
    	for(int k=0;k<n;k++) {
    		if(a[k]<(long)0) {
    			f1[i]=(k+1);
    			i++;
    		}else {
    			f2[j]=(k+1);
    			j++;
    		}
    	}
    	long oddsum=0;
    	if(neg!=0) {
    		oddsum+=f1[1];
    	}
    	long evensum=0;
    	long ans1=0;
    	long count2=0;
    	for(int k=2;k<=neg;k++) {
    		if(k%2==0) {
    			ans1+=oddsum;
    			f3[k]=oddsum;
    			evensum+=(f1[k]-f1[k-1]);
    		}else {
    			ans1+=evensum;
    			oddsum+=(f1[k]-f1[k-1]);
    		f3[k]=evensum;
    		}
    	}
    	out:for(int k=pos;k>=1;k--) {
    		int h=lower_bound(f1,neg,f2[k]);
    	if(h==0) {
    		ans1+=(f2[k]*(f2[k]+1))/2;
    		break out;
    	}else {
    		ans1+=((f2[k]-f1[h])+f3[h]);
    		
    	}
    	}
    	
    	
    	
    	 oddsum=0;
    	 evensum=0;
    	 long ans2=0;
    	 
    	for(int k=1;k<=neg;k++) {
    		if(k%2==0) {
    			evensum+=(f1[k]-f1[k-1]);
    			ans2+=evensum;
    			f3[k]=evensum;
    		}else {
    			oddsum+=(f1[k]-f1[k-1]);
    			ans2+=oddsum;
    		f3[k]=oddsum;
    		}
    	}
    	out:for(int k=pos;k>=1;k--) {
    		int h=lower_bound(f1,neg,f2[k]);
    	if(h==0) {
//    		ans1+=(f2[k]*(f2[k]+1))/2;
    		break out;
    	}else {
    		ans2+=(f3[h]);
    		
    	}
    	}
    	
    	out.println(ans2+" "+ans1);
    	
    	
    	
    	    
		out.close();
       
	}
	
	static class pair1 implements Comparable<pair1>{
		private int a;
		private int b;
		private int c;
		private int d;
		pair1(int a,int b,int c,int d){
			this.a=a;
			this.b=b;
			this.c=c;
			this.d=d;
		}
		public int compareTo(pair1 o) {
			if(this.a<o.a) {
				return 1;
			}else if(this.a==o.a) {
				if(this.b<o.b) {
					return 1;
				}else {
					return -1;
				}
			}else {
				return -1;
			}
				
		}
	}
//	public static pair1[] merge_sort(pair1[] A, int start, int end) {
//		if (end > start) {
//			int mid = (end + start) / 2;
//			pair1[] v = merge_sort(A, start, mid);
//			pair1[] o = merge_sort(A, mid + 1, end);
//			return (merge(v, o));
//		} else {
//			pair1[] y = new pair1[1];
//			y[0] = A[start];
//			return y;
//		}
//	}
//	public static pair1[] merge(pair1 a[], pair1 b[]) {
////		int count=0;
//		pair1[] temp = new pair1[a.length + b.length];
//		int m = a.length;
//		int n = b.length;
//		int i = 0;
//		int j = 0;
//		int c = 0;
//		while (i < m && j < n) {
//			if (a[i].a < b[j].a) {
//				temp[c++] = a[i++];
//			} else {
//				temp[c++] = b[j++];
//			}
//		}
//		while (i < m) {
//			temp[c++] = a[i++];
//		}
//		while (j < n) {
//			temp[c++] = b[j++];
//		}
//		return temp;
//	}
	
	public static int upper_bound(long[] a ,int n,long x) {
		int l=0;
		int r=n+1;
		while(r>l+1) {
			int mid=(l+r)/2;
			if(a[mid]<x) {
				l=mid;
			}else {
				r=mid;
			}
		}
		return r;
				
	}

	
	
	public static int lower_bound(long[] a ,int n,long x) {
		int l=0;
		int r=n+1;
		while(r>l+1) {
			int mid=(l+r)/2;
			if(a[mid]<=x) {
				l=mid;
			}else {
				r=mid;
			}
		}
		return l;
				
	}
	static boolean isValid(int x,int y,int n,int m) {
		if(x>=1 && x<=n && y>=1 && y<=m) {
			return true;
		}else {
			return false;
		}
	}
	public static boolean equal_Sum_Partition(long[] a,int n) {
		 long sum=0;
		 for(int i=1;i<=n;i++) {
			 sum+=a[i];
		 }
		 if(sum%2!=0) {
			 return false;
		 }else {
			 return subset_Sum_Using_Knapsack(a,n,sum/2);
		 }
	 }
	public static boolean subset_Sum_Using_Knapsack(long[] a,int n,long sum) {
		 int[][] dp=new int[n+1][(int) (sum+1)];
		 for(int i=0;i<=n;i++) {
			 dp[i][0]=1;
		 }
		 for(int i=1;i<=n;i++) {
			 for(int j=1;j<=sum;j++) {
				 if(a[i]<=j) {
					 dp[i][j]=Math.max((dp[i-1][j]),(dp[i-1][(int) (j-a[i])]));
				 }else {
					 dp[i][j]=dp[i-1][j];
				 }
			 }
		 }
		 return dp[n][(int) sum]==1;
	 }
	static long[] fac=new long[1000001];
	static void fac() {
		fac[0]=1;
		for(int i=1;i<=1000000;i++) {
			fac[i]=((fac[i-1]%mod)*(i%mod))%mod;
		}
	}
	static ArrayList<Integer>[] f=new ArrayList[2001];
	public static void init(int n) {
		
		for(int j=1;j<=n;j++) {
		for (int l=1; l<=Math.sqrt(j); l++)
        {
            if (j%l==0)
            {
                // If divisors are equal, print only one
                if (j/l == l) {
                    f[j].add(l);}
      
                else { // Otherwise print both
//                    System.out.print(i+" " + n/i + " " );
            f[j].add(l);
            f[j].add(j/l);
                }
                
            }
        }
		
		}
		
	}
	public static int rod_cutting_with_left_right_strategy(int[] a,int n) {
		int[] dp=new int[n+1];
		dp[1]=a[1];
		for(int i=2;i<=n;i++) {
			dp[i]=a[i];
			int left=1;
			int right=i-1;
			while(left<=right) {
				dp[i]=Math.max(dp[left]+dp[right],dp[i]);
			left++;
			right--;
			}
			
		}
		return dp[n];
	}
	public static long[] merge_sort(long[] A, int start, int end) {
		if (end > start) {
			int mid = (end + start) / 2;
			long[] v = merge_sort(A, start, mid);
			long[] o = merge_sort(A, mid + 1, end);
			return (merge(v, o));
		} else {
			long[] y = new long[1];
			y[0] = A[start];
			return y;
		}
	}
	public static long[] merge(long a[], long b[]) {
//		int count=0;
		long[] temp = new long[a.length + b.length];
		int m = a.length;
		int n = b.length;
		int i = 0;
		int j = 0;
		int c = 0;
		while (i < m && j < n) {
			if (a[i] > b[j]) {
				temp[c++] = a[i++];
			
			} else {
				temp[c++] = b[j++];
			}
		}
		while (i < m) {
			temp[c++] = a[i++];
		}
		while (j < n) {
			temp[c++] = b[j++];
		}
		return temp;
	}
	
	public static long[] merge_sort1(long[] A, int start, int end) {
		if (end > start) {
			int mid = (end + start) / 2;
			long[] v = merge_sort1(A, start, mid);
			long[] o = merge_sort1(A, mid + 1, end);
			return (merge1(v, o));
		} else {
			long[] y = new long[1];
			y[0] = A[start];
			return y;
		}
	}
	public static long[] merge1(long a[], long b[]) {
//		int count=0;
		long[] temp = new long[a.length + b.length];
		int m = a.length;
		int n = b.length;
		int i = 0;
		int j = 0;
		int c = 0;
		while (i < m && j < n) {
			if (a[i] > b[j]) {
				temp[c++] = a[i++];
			
			} else {
				temp[c++] = b[j++];
			}
		}
		while (i < m) {
			temp[c++] = a[i++];
		}
		while (j < n) {
			temp[c++] = b[j++];
		}
		return temp;
	}
	
	static long mod=1000000007;
	static class pair2{
		private long a;
		private int b;
		pair2(long a,int b){
			this.a=a;
			this.b=b;
		}
	}
	
}
//	for(int i=2;i<=100000;i++) {
		
//	}
	