题目描述

给定一个大小为 $n$ 的非零整数数列 $a_1, a_2, \ldots, a_n(a_i \neq 0)$。

你需要计算如下两个结果：

1. 存在多少下标对 $(l, r)$ 满足 $1 \le l \le r \le n$ 且 $a_l \cdot a_{l+1} \cdots a_{r-1} \cdot a_r$ 是负数；
2. 存在多少下标对 $(l, r)$ 满足 $1 \le l \le r \le n$ 且 $a_l \cdot a_{l+1} \cdots a_{r-1} \cdot a_r$ 是正数。

即：你需要计算数列 $a$ 的所有子序列中有多少连续子序列包含的元素乘积是负数，有多少是正数。

输入格式

第一行，一个整数 $n(2 \le n \le 2 \cdot 10^5)$。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(-10^9 \le a_i \le 10^9, a_i \neq 0)$，两两之间以一个空格分隔。

输出格式

输出共一行，包含两个整数，以一个空格分隔，分别表示有多少连续子序列对应的元素乘积是负数，以及有多少连续子序列对应的元素乘积是正数。

input1

5
5 -3 3 -1 1

output1

8 7

input2

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

output2

28 27

input3

5
-1 -2 -3 -4 -5

output3

9 6

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 20, -10^3 \le a_i \le 10^3$
• 对于 $60\%$ 的数据，$n \le 2000, -10^6 \le a_i \le 10^6$
• 对于 $100\%$ 的数据，$n \le 2 \cdot 10^5, -10^9 \le a_i \le 10^9, a_i \neq 0$