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.*;
import java.util.*;
import java.awt.*;
public class div585B_up
{
	BufferedReader in;
	PrintWriter ob;
	StringTokenizer st;

	public static void main(String[] args) throws IOException {
		new div585B_up().run();
	}

	void run() throws IOException {
		in=new BufferedReader(new InputStreamReader(System.in));
		ob=new PrintWriter(System.out);
		solve();
		ob.flush();
	}

	void solve() throws IOException {
		int n = ni();
		int a[] = nia(1,n+1);

		
		long ans[] = solver( n , a );
		ob.println(ans[0]+" "+ans[1]);
	}

	long[] solver(int n , int a[]) {
		ArrayList<Integer> list = new ArrayList<>();
		for(int i=1 ; i<=n ; i++) {
			if( a[i] < 0 )
				list.add(i);
		}
		
		long p = (n*1L*(n+1))/2;

		if( list.size() == 0 ) {
			return new long[]{0 , p};
		}

		if( list.size() == 1 ) {
			long left = list.get(0)-1;
			long right = n - list.get(0);
			long ans = left+right+(left*1L*right)+1;
			return new long[]{ans , p-ans};
		}

		long res = 0;
		long dp[]  = new long[list.size()];
		long prefix[] = new long[list.size()];
		long sum = 0;
		for(int i=0 ; i<list.size() ; i++) {
			int e = list.get(i);
			long left =0, right = 0;
			if( i!= list.size()-1 ) {

				left = i==0? (e-1) : ( e - list.get(i-1) - 1 );
				right = list.get(i+1) - e - 1;
				res+=left+right+(left*right)+1;
			} else {
				right = n-list.get(i) ;
				left = e - list.get(i-1)-1;
				res+=left+right+(left*1L*right)+1;
			}

			if( i == 0 || i == 1) {
				dp[i] = left+1;
				prefix[i] = left+1;
			}
			else {
				dp[i] = (prefix[i-2])*(right+1);
				prefix[i]=prefix[i-2]+left+1;
			}

			if( i >= 2 )
			sum+=dp[i];
		
			//System.out.println(i+" "+e+" "+res+" "+sum+" "+" p = "+prefix[i]+" dp ="+dp[i]);
		}
	
		return new long[]{ res+sum , p-res-sum };
	}

	String ns() throws IOException {
		return nextToken();
	}
	long nl() throws IOException {
		return Long.parseLong(nextToken());
	}
	int ni() throws IOException {
		return Integer.parseInt(nextToken());
	}
	double nd() throws IOException {
		return Double.parseDouble(nextToken());
	} 
	String nextToken() throws IOException {
		if(st==null || !st.hasMoreTokens())
			st=new StringTokenizer(in.readLine());
		return st.nextToken();
	}
	int[] nia(int start,int b) throws IOException {
		int a[]=new int[b];
		for(int i=start;i<b;i++)
			a[i]=ni();
		return a;
	}
	long[] nla(int start,int n) throws IOException {
		long a[]=new long[n];
		for (int i=start; i<n ;i++ ) {
			a[i]=nl();
		}
		return a;
	}
}