You are given a sequence a_1, a_2, ..., a_n consisting of n non-zero integers (i.e. a_i ≠ 0). 

You have to calculate two following values:

  1. the number of pairs of indices (l, r) (l ≤ r) such that a_l ⋅ a_{l + 1} ... a_{r - 1} ⋅ a_r is negative; 
  2. the number of pairs of indices (l, r) (l ≤ r) such that a_l ⋅ a_{l + 1} ... a_{r - 1} ⋅ a_r is positive; 

Input

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 a_1, a_2, ..., a_n (-10^{9} ≤ a_i ≤ 10^{9}; a_i ≠ 0) — the elements of the sequence.

Output

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

Examples

Input


5
5 -3 3 -1 1


Output


8 7


Input


10
4 2 -4 3 1 2 -4 3 2 3


Output


28 27


Input


5
-1 -2 -3 -4 -5


Output


9 6

import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;

public class Contest {

    final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

    public static void main(String[] args) {
        new Contest().run();
    }

    void init() throws FileNotFoundException {
        if (ONLINE_JUDGE) {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        } else {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    public void run() {
        try {
            long t1 = System.currentTimeMillis();
            init();
            solve();
            out.close();
            long t2 = System.currentTimeMillis();
            System.err.println("Time(ms) = " + (t2 - t1));
        } catch (Exception e) {
            e.printStackTrace(System.err);
            System.exit(-1);
        }
    }

    class MyComparator implements Comparable<MyComparator> {

        int x;
        int y;

        public MyComparator(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(MyComparator a) {
            if (x == a.x) {
                return (y - a.y);
            }
            return x - a.x;
        }
    }

    public static boolean isPrime(int num) {
        if (num > 2 && num % 2 == 0) {
            //System.out.println(num + " is not prime");
            return false;
        }
        int top = (int) Math.sqrt(num) + 1;
        for (int i = 3; i < top; i += 2) {
            if (num % i == 0) {
                //System.out.println(num + " is not prime");
                return false;
            }
        }
        //System.out.println(num + " is prime");
        return true;
    }

    private static int lowerBound(int[] a, int low, int high, int element) {
        while (low < high) {
            int middle = low + (high - low) / 2;
            if (element > a[middle]) {
                low = middle + 1;
            } else {
                high = middle;
            }
        }
        return low;
    }

    private static int upperBound(int[] a, int low, int high, int element) {
        while (low < high) {
            int middle = low + (high - low) / 2;
            if (a[middle] > element) {
                high = middle;
            } else {
                low = middle + 1;
            }
        }
        return low;
    }

    public void solveC() throws IOException {

        int n = readInt();
        String s = readString();
        String t = readString();
        String[] sArray = s.split("");
        String[] tArray = t.split("");

        int[] delta = new int[n];
        Arrays.fill(delta, 0);

        int num1 = 0;
        int num2 = 0;
        List<Integer> place1 = new ArrayList<>();
        List<Integer> place2 = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!sArray[i].equals(tArray[i])) {
                if (sArray[i].equals("a")) {
                    delta[i] = 1;
                    place1.add(i + 1);
                    num1++;
                } else {
                    delta[i] = -1;
                    place2.add(i + 1);
                    num2++;
                }
            }
        }

        if (Math.abs(num1 - num2) % 2 != 0) {
            System.out.println("-1");
            return;
        }

        int num = 0;
        StringBuilder result = new StringBuilder();
        //result.append(num1 / 2 + num2 / 2 + Math.abs(num1 - num2)*2).append("\n");

        int additive1 = -1;
        int additive2 = -1;
        for(int i=0; i<num1; i+=2) {
            if(i == num1 -1) {
                additive1 = i;
                break;
            }
            result.append(place1.get(i)).append(" ").append(place1.get(i+1)).append("\n");
            num++;
        }
        for(int i=0; i<num2; i+=2) {
            if(i == num2 -1) {
                additive2 = i;
                break;
            }
            result.append(place2.get(i)).append(" ").append(place2.get(i+1)).append("\n");
            num++;
        }
        if(additive1 != -1) {
            result.append(place1.get(additive1)).append(" ").append(place1.get(additive1)).append("\n");
            result.append(place1.get(additive1)).append(" ").append(place2.get(additive2)).append("\n");
            num+=2;
        }
        StringBuilder last = new StringBuilder(String.valueOf(num)).append("\n");
        last.append(result);
        last.delete(last.length()-1, last.length());
        System.out.println(last.toString());
        //System.out.println("wtf");
    }

    public void solve() throws IOException {

        int n = readInt();
        long[] array = new long[n];
        for (int i = 0; i < n; i++) {
            int res = readInt();
            //System.out.println(res);
            if (res > 0) {
                array[i] = 1;
            } else {
                array[i] = -1;
            }
        }
        long left = 0;
        long right = 0;
        long result = 1;
        for (int i = 0; i < n; i++) {
            result = result * array[i];
            if (result > 0) {
                right++;
            } else {
                left++;
            }
        }

        long leftC = left;
        long rightC = right;
        for (int i = 0; i < n-1; i++) {
            if (array[i] > 0) {
                rightC--;
                right += rightC;
                left += leftC;
            } else {
                leftC--;
                long bia = leftC;
                leftC = rightC;
                rightC = bia;
                right += rightC;
                left += leftC;
            }
            //System.out.println(leftC + "left");
            //System.out.println(rightC + "rightC");
        }
        System.out.println(left + " " + right);
    }

    public void solveA() throws IOException {

        int a1 = readInt();
        int a2 = readInt();
        int k1 = readInt();
        int k2 = readInt();
        int n = readInt();

        int min = 0;
        int max = 0;
        int nCopy = n;
        int a1Copy = a1;
        int a2Copy = a2;
        if (k1 < k2) {
            while (a1Copy > 0 && nCopy >= k1) {
                a1Copy--;
                nCopy -= k1;
                max++;
            }
            while (a2Copy > 0 && nCopy >= k2) {
                a2Copy--;
                nCopy -= k2;
                max++;
            }
        } else {
            while (a2Copy > 0 && nCopy >= k2) {
                a2Copy--;
                nCopy -= k2;
                max++;
            }
            while (a1Copy > 0 && nCopy >= k1) {
                a1Copy--;
                nCopy -= k1;
                max++;
            }
        }

        n -= a1 * (k1 - 1) + a2 * (k2 - 1);
        min = Math.max(0, n);
        System.out.println(min + " " + max);
    }

    /**
     *
     * @param a
     * @param b
     * @return
     */
    private BigInteger lcm(BigInteger a, BigInteger b) {
        return a.multiply(b.divide(a.gcd(b)));
    }

}
