1215B. B. The Number of Products

CF1215B. The Number of Products

时限: 2 秒 | 内存: 256 MB | 输入: 标准输入 | 输出: 标准输出

给出一个由$n$个非零整数构成的序列$a_1,a_2,\dots,a_n$。

你需要计算下列两个值：

1.下标对$(l,r)(l\le r)$使得$a_la_{l+1}\dots*a_r$为负数；

2.下标对$(l,r)(l\le r)$使得$a_la_{l+1}\dots*a_r$为正数；

输入格式

第一行包含一个整数$n(1\le n\le2*10^5)$，表示序列的元素个数。

第二行包含$n$个非零整数$a_i(-10^9\le a_i\le10^9;a_i\neq 0)$，表示数列中的各个元素。

输出格式

输出两个整数，分别表示乘积为负的子区间个数和乘积为正的子区间个数。

样例输入 1

5
5 -3 3 -1 1

样例输出 1

8 7

样例输入 2

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

样例输出 2

28 27

样例输入 3

5
-1 -2 -3 -4 -5

样例输出 3

9 6