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
// package name;
import java.io.*;
import java.util.*;

public class M {

	static long longmx = 9223372036854775807l;
	static long longmn = -9223372036854775808l;
	static int intmx = 2147483647;
	static int intmn = -2147483648;
	static Scanner s = new Scanner(System.in);
	static PrintWriter out = new PrintWriter(System.out);

	public static void main(String[] args) {
		int t = 1;
		//t = s.nextInt();
		StringBuffer sb = new StringBuffer();
		while (t > 0) {
			t--;
			int n = iinp();
			//int c = iinp();
			int arr[] = iinparr(n, 0);
			int p[] = new int[n];
			int neg[] = new int[n];
			if(arr[0] >= 0) p[0]++;
			else neg[0]++;
			long psum = p[0], nsum = neg[0];
			for(int i = 1; i < n; i++) {
				if(arr[i] >= 0) {
					p[i] = p[i - 1] + 1;
					neg[i] = neg[i - 1];
				}
				else {
					p[i] = neg[i - 1];
					neg[i] = p[i - 1] + 1;
				}
				psum += p[i];
				nsum += neg[i];
			}
			sb.append(nsum + " " + psum);
		}
		out.print(sb);
		out.flush();
	}

	static int iinp() {
		return s.nextInt();
	}

	static long linp() {
		return s.nextLong();
	}

	static double dinp() {
		return s.nextDouble();
	}

	static String sinp() {
		return s.next();
	}

	static String slinp() {
		return s.nextLine();
	}

	static int[] idecarr(int n) {
		return new int[n];
	}

	static long[] ldecarr(int n) {
		return new long[n];
	}

	static String[] sdecarr(int n) {
		return new String[n];
	}

	static int[][] idec2darr(int n, int m) {
		return new int[n][m];
	}

	static long[][] ldec2darr(int n, int m) {
		return new long[n][m];
	}

	static int[] iinparr(int n, int st) {
		int a[] = idecarr(n);
		for (int i = st; i < st + n; i++) {
			a[i] = iinp();
		}
		return a;
	}

	static long[] linparr(int n, int st) {
		long a[] = ldecarr(n);
		for (int i = st; i < st + n; i++) {
			a[i] = linp();
		}
		return a;
	}

	static int[][] iinp2darr(int n, int m) {
		int a[][] = idec2darr(n, m);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				a[i][j] = iinp();
			}
		}
		return a;
	}

	static long[][] linp2darr(int n, int m) {
		long a[][] = ldec2darr(n, m);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				a[i][j] = iinp();
			}
		}
		return a;
	}

	static long min(long... a) {
		long min = longmx;//Long.MAX_VALUE;
		for (long i : a) {
			if (i < min)
				min = i;
		}
		return min;
	}

	static long max(long... a) {
		long max = longmn;//Long.MIN_VALUE;
		for (long i : a) {
			if (i > max)
				max = i;
		}
		return max;
	}

	static long gcd(long a, long b) {
		if (b == 0)
			return a;
		return gcd(b, a % b);
	}

	static void sort(int a[]) {
		Arrays.sort(a);
	};

	static void sort(int a[], int st, int e) {
		Arrays.sort(a, st, e);
	};

	static void sort(long a[]) {
		Arrays.sort(a);
	};

	static void sort(long a[], int st, int e) {
		Arrays.sort(a, st, e);
	};

	static void sort(String a[]) {
		Arrays.sort(a);
	};

	static void sort(String a[], int st, int e) {
		Arrays.sort(a, st, e);
	};

	static StringBuffer printarr(long a[]) {
		StringBuffer ans = new StringBuffer();
		for (long i : a)
			ans.append(i + " ");
		ans.append("\n");
		return ans;
	}

	static StringBuffer printarr(int a[]) {
		StringBuffer ans = new StringBuffer();
		for (int i : a)
			ans.append(i + " ");
		ans.append("\n");
		return ans;
	}

}

class Pair {
	long a, b;

	Pair(long x, long y) {
		a = x;
		b = y;
	}
}

/*
 * to sort the array of pair
 * Compare obj = new Compare();
 * obj.compare(arr);
 */
class Compare {

	static void compare(Pair arr[]) {
		Arrays.sort(arr, new Comparator<Pair>() {
			@Override
			public int compare(Pair p1, Pair p2) {
				if (p1.a != p2.a)
					return (p1.a - p2.a > 0) ? 1 : -1;
				else
					return (p1.b - p2.b > 0) ? 1 : -1;
			}
		});
	}
}
