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.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;


public class Main {
    
final static IOFast io = new IOFast();
    
    public static void main(String args[]) throws IOException
    {
        int N = io.nextInt();
        
        
        
        
        
        LinkedList<Integer> ll = new LinkedList<Integer>(); 

        for(int i=0; i<N; i++)
        {
            
            ll.addLast(io.nextInt());
            
        }
        int se = 0;
        int di = 0;
        
        int turn = 0;
        while(!ll.isEmpty())
        {
            
            Integer f = ll.getFirst();
            Integer e = ll.getLast();
            
            if(f>e)
            {
                if(turn==0)
                    se += ll.removeFirst();
                else
                    di +=ll.removeFirst();
                
            }
            else
            {
                if(turn==0)
                    se += ll.removeLast();
                else
                    di +=ll.removeLast();
                
                
            }
        
            turn = (turn+1)%2;
        }
        
        System.out.println(se+" "+di);
    }

}
class IOFast {
    private BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    private PrintWriter out = new PrintWriter(System.out);

    void setFileIO(String ins, String outs) throws IOException {
        in = new BufferedReader(new FileReader(ins));
        out = new PrintWriter(new FileWriter(outs));
    }

    //      private static final int BUFFER_SIZE = 50 * 200000;
    private static int pos, readLen;
    private static final char[] buffer = new char[1024 * 8];
    private static final char[] str = new char[500000*8*2];
    private static boolean[] isDigit = new boolean[256];
    private static boolean[] isSpace = new boolean[256];
    private static boolean[] isLineSep = new boolean[256];

    static {
        for(int i = 0; i < 10; i++) { isDigit['0' + i] = true; }
        isDigit['-'] = true;
        isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true;
        isLineSep['\r'] = isLineSep['\n'] = true;
    }

    public int read() throws IOException {
        if(pos >= readLen) {
            pos = 0;
            readLen = in.read(buffer);
            if(readLen <= 0) { throw new IOException(); }
        }
        return buffer[pos++];
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(nextString());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(nextString());
    }

    public char nextChar() throws IOException {
        while(true) {
            final int c = read();
            if(!isSpace[c]) { return (char)c; }
        }
    }
    
    int reads(char[] cs, int len, boolean[] accept) throws IOException {
        try {
            while(true) {
                final int c = read();
                if(accept[c]) { break; }
                cs[len++] = (char)c;
            }
        }
        catch(IOException e) { ; }
        
        return len;
    }

    public char[] nextLine() throws IOException {
        int len = 0;
        str[len++] = nextChar();
        len = reads(str, len, isLineSep);
        
        try {
            if(str[len-1] == '\r') { len--; read(); }
        }
        catch(IOException e) { ; }
        
        return Arrays.copyOf(str, len);
    }

    public String nextString() throws IOException {
        return new String(next());
    }

    public char[] next() throws IOException {
        int len = 0;
        str[len++] = nextChar();
        len = reads(str, len, isSpace);
        return Arrays.copyOf(str, len);
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(nextString());
    }

    public Long[] nextLongArray(final int n) throws IOException {
        final Long[] res = new Long[n];
        for(int i = 0; i < n; i++) {
            res[i] = nextLong();
        }
        return res;
    }

    public int[] nextIntArray(final int n) throws IOException {
        final int[] res = new int[n];
        for(int i = 0; i < n; i++) {
            res[i] = nextInt();
        }
        return res;
    }

    public int[][] nextIntArray2D(final int n, final int k) throws IOException {
        final int[][] res = new int[n][];
        for(int i = 0; i < n; i++) {
            res[i] = nextIntArray(k);
        }
        return res;
    }

    public double[] nextDoubleArray(final int n) throws IOException {
        final double[] res = new double[n];
        for(int i = 0; i < n; i++) {
            res[i] = nextDouble();
        }
        return res;
    }

}
