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
'''input
5
-1 -2 -3 -4 -5
'''
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict
from bisect import bisect_left


def get_aux(arr):
	aux = []
	temp = []
	for i in range(len(arr)):
		if arr[i] > 0:
			temp.append(arr[i])
		elif arr[i] < 0:
			if len(temp) > 0:
				aux.append(temp)
				temp = []
			else:
				pass
	if len(temp) > 0:
		aux.append(temp)

	aux2 = []
	for temp in aux:
		aux2.append(len(temp))
	return aux2


def get_descrete(num):
	return num + (num * (num - 1)) // 2

def change(num):
	if num == 0:
		return 1

	else:
		return 0

# main starts
n = int(stdin.readline().strip())
arr = list(map(int, stdin.readline().split()))

negate = [0] *n
if arr[0] < 0:
	negate[0] = 1

for i in range(1, n):
	if arr[i] < 0:
		negate[i] = negate[i - 1] + 1
	else:
		negate[i] = negate[i - 1]


oe = [[0 for x in range(2)] for y in range(n)]
if negate[-1] % 2 == 0:
	oe[-1][1] += 1
else:
	oe[-1][0] += 1
for i in range(n - 2, -1, -1):
	oe[i][0] = oe[i + 1][0]
	oe[i][1] = oe[i + 1][1]
	if negate[i] % 2 == 0:
		oe[i][1] += 1

	else:
		oe[i][0] += 1

ans = 0
polarity = 0
for i in range(n):
	if polarity == 0:
		if arr[i] > 0:
			ans += oe[i][1]
		else:
			if i + 1 < n:
				ans += oe[i + 1][1]
			polarity = change(polarity)

	else:
		if arr[i] > 0:
			if i + 1 < n:
				ans += oe[i + 1][0]
			ans += 1
		else:
			if i + 1 < n:
				ans += oe[i + 1][0]
			polarity = change(polarity)


print((n * (n + 1))// 2 - ans, ans)