给定一个序列 $$$a_1, a_2, \dots, a_n$$$,由 $$$n$$$ 非零整数组成(即 $$$a_i \ne 0$$$)。
您必须计算以下两个值:
1. 使 $$$a_l \cdot a_{l + 1} \dots a_{r - 1} \cdot a_r$$$ 为负的索引对 $$$(l, r)$$$ $$$(l \le r)$$$ 的数量;
2. 使 $$$a_l \cdot a_{l + 1} \dots a_{r - 1} \cdot a_r$$$ 为正的索引对 $$$(l, r)$$$ $$$(l \le 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)$$$ — 序列的元素。
输出
打印两个整数 - 分别具有负乘积的子段数和具有正乘积的子段数。
示例
输入 #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