题目描述

在一个神奇的世界里，魔法元素是非常重要的，它们有着巨大的能量。ak_coding也是这个世界的一名著名的魔法师，他掌握了许多神奇的魔法。但他总是想知道，使用他所拥有的魔法元素，是否有足够的能量施展出一种强大的魔法。 于是，他将所有魔法元素排成一行，从左到右第 $i$个魔法元素的能量值是一个非零整数$a_i$ 。他发现，他可以选出一段连续的魔法元素，将它们的能量值乘起来得到一个总能量值。如果这个总能量值大于零，他就能施展出一种白魔法，否则他只能施展出黑魔法。 现在ak_coding想知道施展一个白魔法或黑魔法的方案数分别有多少。两个方案不同是指挑选的连续区间不同。

输入描述

第一行有一个整数$n$( $1\le n \le 2\times 10^5$)，表示魔法元素的个数。

第二行有 $n$个整数 $a_1,a_2,...,a_n(-10^9 \le a_i \le 10^9)$，代表魔法元素的能量值。

输出描述

输出两个整数，分别表示施展一个黑魔法和施展一个白魔法的方案数。

样例

输入

6
6 -1 -3 5 3 -5

输出

10 11