B. The Number of Products)厉害

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

给你一个由n个非零整数（即ai≠0）组成的序列a1,a2,...,an。

你必须计算以下两个值。

指数(l,r)的数目(l≤r)，使al⋅al+1...ar-1⋅ar为负数。
使得al⋅al+1...ar-1⋅ar为正数的一对索引(l,r)(l≤r)的数量。
输入
第一行包含一个整数n（1≤n≤2⋅105）--序列中的元素数。

第二行包含n个整数a1,a2,...,an (-109≤ai≤109;ai≠0) - 序列的元素。

输出
打印两个整数 - 负积的子段数和正积的子段数，分别为。

意思：

题目意思是说输出负积子段数和正积子段数。既然都是积，那么只要出现负数就可能改变积的正负，也就是说在遍历的时候要考虑出现负数的情况，如果只存在正数，那么直接1+2+3+。。。+n就能得到答案。

 

如果出现负数那么就交换正负数的计数，然后在负数奇数上面+1；

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<stack>
#include<string>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<cstring>
#include<queue>
#include<set>
#include<stdlib.h>
#define dbug cout<<"hear!"<<endl;
#define rep(a,b) for(int i=a;i<=b;i++)
#define rrep(a,b) for(int j=a;j<=b;j++)
#define per(a,b) for(int i=a;i>=b;i--)
#define pper(a,b) for(int j=a;j>=b;j--)
#define no cout<<"NO"<<endl;
#define yes cout<<"YES"<<endl;
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 2e5 + 100;
const int  INF = 0x3f3f3f3f;
ll gcdd(ll a, ll b)
{if (b) while ((a %= b) && (b %= a));return a + b;
}
const int mod = 998244353;
ll t, n, m, a, b, c, x, k, cnt, ans, ant, sum, q, p, idx;
ll arr[N], brr[N], crr[N];
ll axx[2000][2000];
bool book[N];
char s[N];int main()
{cin >> n;ant = 0;cnt = 0;ans = 0;ll zheng = 0, fu = 0;rep(1, n){cin >> x;if (x > 0){ant++;}else{swap(ant, cnt);cnt++;}zheng += ant;fu += cnt;}cout << fu << ' ' << zheng;
}