每个测试的时间限制：$2$ 秒 内存限制：$256$ 兆字节

题目描述

给定一个由 $n$ 个非零整数（即 $a_i \neq 0$）组成的序列 $a_1, a_2, \dots, a_n$。

你需要计算以下两个值：

有多少对下标 $(l, r)$（$l \le r$），使得 $a_l \cdot a_{l+1} \dots a_{r-1} \cdot a_r$ 为 负；

有多少对下标 $(l, r)$（$l \le r$），使得 $a_l \cdot a_{l+1} \dots a_{r-1} \cdot a_r$ 为 正。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）——序列中元素的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^9 \le a_i \le 10^9$；$a_i \neq 0$）——序列的元素。

输出格式

输出两个整数——乘积为负的子段数量和乘积为正的子段数量。

5
5 -3 3 -1 1

8 7

数据规模与约定

对于 $100\%$ 的数据，$0 \le n \le 10^7$。