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.util.*;


public class Q1 {


    public static void main(String[] args) {

        InputReader in=new InputReader();
        int N=in.nextInt();


        //int arr[]=new int[N];



        long neg=0,pos=0,p=0,n=0;

        for(int i=0;i<N;i++){

            int aa=in.nextInt();
            if(aa>=0) {
                p++;
            }else{
                long temp=n;
                n=p;
                p=temp;
                n++;
            }


            pos+=p;
            neg+=n;


        }

        System.out.println(neg+" "+pos);





    }


//    public static void main(String[] args) {
//
//        InputReader in = new InputReader();
//        int N = in.nextInt(), M = in.nextInt();
//
//        int arr[][] = new int[M][2];
//
//        N=M;
//        int i = 0;
//        while (M-- > 0) {
//            int a = in.nextInt(), b = in.nextInt();
//            arr[i][0] = Math.min(a, b);
//            arr[i][1] = Math.max(a, b);
//            i++;
//        }
//
//        Arrays.sort(arr, new Comparator<int[]>() {
//            public int compare(int o1[], int o2[]) {
//                int temp = Integer.compare(o1[0], o2[0]);
//                if (temp != 0)
//                    return temp;
//
//                return Integer.compare(o1[1], o2[1]);
//
//            }
//        });
//
//        int ans = 0;
//        HashSet<Integer> map = new HashSet<>();
//
//        for (i = 0; i < N; i++) {
//            int a = arr[i][0], b = arr[i][1];
//      //      System.out.println(a+"   "+b);
//            if (map.contains(a) && map.contains(b)) {
//                ans++;
//            } else {
//                map.add(a);
//                map.add(b);
//            }
//
//
//        }
//
//        map.clear();
////        HashSet<Integer> map = new HashSet<>();
//
//        int ans1=0;
//        for (i = N-1; i>=0; i--) {
//            int a = arr[i][0], b = arr[i][1];
//            //      System.out.println(a+"   "+b);
//            if (map.contains(a) && map.contains(b)) {
//                ans1++;
//            } else {
//                map.add(a);
//                map.add(b);
//            }
//
//
//        }
//
//
//        System.out.println(Math.min(ans,ans1));
//
//    }

//    public static void main(String[] args) {
//
//        InputReader in = new InputReader();
//
//        int t = in.nextInt();
//
//
//
//        while (t-- > 0) {
//            String str = in.next();
//            char arr[] = str.toCharArray();
//
//            int ans = 0;
//            for (int i = str.length()-1; i >=0; i--) {
//                int var=Math.max(0,i-32);
//                long pow=0,res=0;
//                for(int j=i;j>=var;j--){
//
//                    if(pow==0)
//                        pow=1;
//                    else
//                        pow=pow*2;
//
//                    if(arr[j]=='1') {
//                         res =res+pow;
//                    }
//
//                    if(res==(i-j+1)) {
//                        ans++;
//                     //   System.out.println(res+"  "+i+"   "+j);
//                    }
//                }
//            }
//
//            System.out.println(ans);
//        }
//    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public int[] shuffle(int[] arr) {
            Random r = new Random();
            for (int i = 1, j; i < arr.length; i++) {
                j = r.nextInt(i);
                arr[i] = arr[i] ^ arr[j];
                arr[j] = arr[i] ^ arr[j];
                arr[i] = arr[i] ^ arr[j];
            }
            return arr;
        }

        public InputReader() {
            reader = new BufferedReader(new InputStreamReader(System.in), 32768);
            tokenizer = null;
        }

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(System.in), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public char nextChar() {
            return next().charAt(0);
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }


    }

}



