题目：

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

You have to calculate two following values:

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

Input

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

The second line contains ?n integers ?1,?2,…,??a1,a2,…,an (−109≤??≤109;??≠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

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

 

解题思路：

（1）dp法：

dp1[i] 表示以a[i]为区间末尾区间积为正的区间左端点数目

dp2[i]表示以a[i]为区间结尾区间积为负的区间左端点数目

遍历数组，当a[i]为正时，更新dp1[i] = dp1[i-1]+1，dp2[i]继承dp2[i-1]; 当a[i]为负时， 更新dp1[i] = dp2[i-1], dp2[i]=dp1[i-1]+1.

在遍历数组时同时计数统计答案。

（2）推导法：因为不会dp，瞎推了下，懒得讲了 ，有一点点小复杂

直接记录负数间的正数个数，然后求区间内包含1，3，5。。2n+1个负数的方法数，统计答案的时候用到了前缀和，让总的区间数减去乘积为负数的区间数得到乘积为正数的区间数。

 

ac代码：

dp法：来自队友wjx

（2）推导法：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+100;
typedef long long ll;
ll a[maxn], b[maxn];
ll sum[maxn];
vector<int> pos;
int main()
{
   //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
   ll n;
   scanf("%lld", &n);
   ll fu = 0;
   ll all = n*(n+1)/2;
    for(int i = 1; i <= n; i++)
   {
       scanf("%lld", &a[i]);
       if(a[i] < 0) pos.push_back(i);
   }
   for(int i = 0; i < pos.size(); i++)
   {
       if(i == 0) b[i+1] = pos[i]-1;
       else b[i+1] = pos[i] - pos[i-1] - 1;
   }
   if(pos.size() >=1 ) b[pos.size()+1] = n - pos[pos.size()-1];
   for(int i = 1; i <= pos.size()+1; i++)
   {
       if(i == 1) sum[1] = b[1];
       else if(i == 2) sum[2] = b[2];
       else sum[i] = sum[i-2] + (ll)b[i];
   }
   for(int i = 2; i <= pos.size()+1; i++)
   {
       int t = i / 2;
       fu += (sum[i-1] + t)* (b[i]+1);
   }
   printf("%lld %lld\n", fu, all-fu);
    return 0;
}