链接：https://codeforces.com/contest/1215/problem/B

You are given a sequence a1,a2,…,ana1,a2,…,an consisting of nn non-zero integers (i.e. ai≠0ai≠0).

You have to calculate two following values:

  1. the number of pairs of indices (l,r)(l,r) (l≤r)(l≤r) such that al⋅al+1…ar−1⋅aral⋅al+1…ar−1⋅ar is negative;
  2. the number of pairs of indices (l,r)(l,r) (l≤r)(l≤r) such that al⋅al+1…ar−1⋅aral⋅al+1…ar−1⋅ar is positive;

Input

The first line contains one integer nn (1≤n≤2⋅105)(1≤n≤2⋅105) — the number of elements in the sequence.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (−109≤ai≤109;ai≠0)(−109≤ai≤109;ai≠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

Copy

5
5 -3 3 -1 1

output

Copy

8 7

input

Copy

10
4 2 -4 3 1 2 -4 3 2 3

output

Copy

28 27

input

Copy

5
-1 -2 -3 -4 -5

output

Copy

9 6

思路：

O（n）算法才能过-_-!答案要用long long 存，简单来说就是按序遍历，记录他可以组成的正数个数和负数个数，并且在s1,s2中累加，遇到正数时只需将前一个状态继承并++正数个数即可，如果遇到负数，则需调换正数和负数个数，并++负数个数

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int maxn=1e6+5;
long long n,s1=0,s2=0,a1=0,a2=0,c;
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		if(x>0)
		{
			a1++;
		}
		else
		{
			c=a2;
			a2=a1;
			a1=c;
			a2++;
		}
		s1+=a1;
		s2+=a2;
	}
	printf("%lld %lld",s2,s1);
}