You are given a sequence a1,a2,…,an consisting of n non-zero integers (i.e. ai≠0). You have to calculate two following values: the number of pairs of indices (l,r) (l≤r) such that al*al+1…ar-1*ar is negative; the number of pairs of indices (l,r) (l≤r) such that al*al+1…ar-1*ar is positive; 注：a后面跟的是下标

The first line contains one integer n (1≤n≤2*10^5) — the number of elements in the sequence. The second line contains n integers a1,a2,…,an (10^9≤ai≤10^9;ai≠0) — the elements of the sequence.

Print two integers — the number of subsegments with negative product and the number of subsegments with positive product, respectively.

(1)
5
5 -3 3 -1 1


(2)
10
4 2 -4 3 1 2 -4 3 2 3


(3)
5
-1 -2 -3 -4 -5

(1)
8 7


(2)
28 27

(3)
9 6