Sereja and Dima play a game. The rules of the game are very simple. The players have n cards in a row. Each card contains a number, all numbers on the cards are distinct. The players take turns, Sereja moves first. During his turn a player can take one card: either the leftmost card in a row, or the rightmost one. The game ends when there is no more cards. The player who has the maximum sum of numbers on his cards by the end of the game, wins.

Sereja and Dima are being greedy. Each of them chooses the card with the larger number during his move.

Inna is a friend of Sereja and Dima. She knows which strategy the guys are using, so she wants to determine the final score, given the initial state of the game. Help her.

Input

The first line contains integer n (1 ≤ n ≤ 1000) — the number of cards on the table. The second line contains space-separated numbers on the cards from left to right. The numbers on the cards are distinct integers from 1 to 1000.

Output

On a single line, print two integers. The first number is the number of Sereja's points at the end of the game, the second number is the number of Dima's points at the end of the game.

Examples

Input

4
4 1 2 10


Output

12 5


Input

7
1 2 3 4 5 6 7


Output

16 12

Note

In the first sample Sereja will take cards with numbers 10 and 2, so Sereja's sum is 12. Dima will take cards with numbers 4 and 1, so Dima's sum is 5.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

public class c223a {
	
	static class TaskA
    {
        public void solve(int testNumber, InputReader in, PrintWriter out) 
        {
           int n=in.nextInt();
           int sums=0,sumd=0;
           int p=0;
           int arr[]=new int[n];
           for(int i=0;i<n;i++)
           {
        	   arr[i]=in.nextInt();
           }
           int i=0;
           int j=n-1;
           while(i<=j)
           {
        	   if(arr[i]>arr[j]&p==0)
        	   {
        		   p=1;
        		   sums+=arr[i];
        		   i++;
        	   }
        	   else if(arr[i]<=arr[j]&p==0)
        	   {
        		   p=1;
        		   sums+=arr[j];
        		   j--;
        	   }
        	   else if(arr[i]>arr[j]&p==1)
        	   {
        		   p=0;
        		   sumd+=arr[i];
        		   i++;
        	   }
        	   else if(arr[i]<=arr[j]&p==1)
        	   {
        		   p=0;
        		   sumd+=arr[j];
        		   j--;
        	   }
           }
           out.println(sums+" "+sumd);
        }
    }
       
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(1, in, out);
        out.close();
    }
    
  
    
    /* java.util.Arrays.sort(array_name,new java.util.Comparator<int[]>(){
    public int compare(int[] a, int[] b) {
        return Integer.compare(a[0], b[0]);
    }}); */
    
    static void radixSort(int[] xs){
		int[] cnt = new int[(1<<16)+1];
		int[] ys = new int[xs.length];	
		for(int j = 0; j <= 16; j += 16) 
		{	Arrays.fill(cnt, 0);
			for(int x : xs) { cnt[(x>>j&0xFFFF)+1]++; }
			for(int i = 1; i < cnt.length; i++) { cnt[i] += cnt[i-1]; }
			for(int x : xs) { ys[cnt[x>>j&0xFFFF]++] = x; }
			{ final int[] t = xs; xs = ys; ys = t; }   }
		if(xs[0] < 0 || xs[xs.length - 1] >= 0) 
			return;
		int i, j, c;
		for(i = xs.length - 1, c = 0; xs[i] < 0; i--, c++) { ys[c] = xs[i]; }
		for(j = xs.length - 1; i >= 0; i--, j--) { xs[j] = xs[i]; }
		for(i = c - 1; i >= 0; i--) { xs[i] = ys[c-1-i]; }
	}
   
    static long min(long x,long y){return x<y?x:y;}
    static long min(long x,long y,long z){return x<y?(x<z?x:z):(y<z?y:z);}
    static long min(long n1,long n2,long n3,long n4){
    	return n1<n2?(n1<n3?(n1<n4?n1:n4):(n3<n4?n3:n4)):(n2<n3?(n2<n4?n2:n4):(n3<n4?n3:n4));}
    static long max(long x,long y){return x>y?x:y;}
    static long max(long x,long y,long z){return x>y?(x>z?x:z):(y>z?y:z);}
    static long max(long n1,long n2,long n3,long n4){
    	return n1>n2?(n1>n3?(n1>n4?n1:n4):(n3>n4?n3:n4)):(n2>n3?(n2>n4?n2:n4):(n3>n4?n3:n4));}
    static int min(int x,int y){return x<y?x:y;}
    static int min(int x,int y,int z){return x<y?(x<z?x:z):(y<z?y:z);}
    static long min(int n1,int n2,int n3,int n4){
    	return n1<n2?(n1<n3?(n1<n4?n1:n4):(n3<n4?n3:n4)):(n2<n3?(n2<n4?n2:n4):(n3<n4?n3:n4));}
    static int max(int x,int y){return x>y?x:y;}
    static int max(int x,int y,int z){return x>y?(x>z?x:z):(y>z?y:z);}
    static long max(int n1,int n2,int n3,int n4){
    	return n1>n2?(n1>n3?(n1>n4?n1:n4):(n3>n4?n3:n4)):(n2>n3?(n2>n4?n2:n4):(n3>n4?n3:n4));}
    
    static long sumarr(int arr[],int n1,int n2){
    	long sum=0; for(int i=n1-1;i<n2;i++) sum=sum+arr[i];  return sum; }
    
    
     
//**************************************Reader Class*********************************************//
    
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 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 String nextLine() {
			String fullLine=null;
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					fullLine=reader.readLine();
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
				return fullLine;
			}
			return fullLine;
		}

        public int nextInt() {
            return Integer.parseInt(next());
        }
        
        public long nextLong() {
        	return Long.parseLong(next());
        }
        
        public double nextDouble() {
        	return Double.parseDouble(next());
        }

    }
}