题目描述

现在有一个由 $n$ 个非零整数组成的序列 $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$ 的乘积是正数，有多少是负数。

但是，白熊不想再花费力气去统计他们的数量了，于是想让聪明的你完成这项艰巨的任务。

输入

第一行包含一个整数 $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$）—— 序列中的元素。

输出

打印两个整数 —— 分别是正乘积子段的数量和负乘积子段的数量。

input

10
-1 -9 1 -10 10 10 -9 -6 -9 1

output

25 30