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.*;
import java.math.*;
import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;


public class Main {

    InputReader input;
    PrintWriter output;

    void run(){
        output = new PrintWriter(new OutputStreamWriter(System.out));
        input = new InputReader(System.in);
        solve();
        output.flush();
    }

    public static void main(String[] args){
        new Main().run();
    }
    
    
    void solve() {
        int n = input.ni();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = input.ni();
        }
        int start = 0;
        int end = n-1;
        int sereja = 0;
        int dima = 0;
        for(int i = 0; i < n; i++) {
            if((i&1) == 0) {
                sereja += (a[start] > a[end] ? a[start++] : a[end--]);
            }
            else {
                dima += (a[start] > a[end] ? a[start++] : a[end--]);
            }
        }
        output.println(sereja+" "+dima);
    }
    
    class InputReader {
        private boolean finished = false;
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
                this.stream = stream;
        }

        public int read() {
                if (numChars == -1)
                        throw new InputMismatchException();
                if (curChar >= numChars) {
                        curChar = 0;
                        try {
                                numChars = stream.read(buf);
                        } catch (IOException e) {
                                throw new InputMismatchException();
                        }
                        if (numChars <= 0)
                                return -1;
                }
                return buf[curChar++];
        }

        public int peek() {
                if (numChars == -1)
                        return -1;
                if (curChar >= numChars) {
                        curChar = 0;
                        try {
                                numChars = stream.read(buf);
                        } catch (IOException e) {
                                return -1;
                        }
                        if (numChars <= 0)
                                return -1;
                }
                return buf[curChar];
        }

        public int ni() {
                int c = read();
                while (isSpaceChar(c))
                        c = read();
                int sgn = 1;
                if (c == '-') {
                        sgn = -1;
                        c = read();
                }
                int res = 0;
                do {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public long nl() {
                int c = read();
                while (isSpaceChar(c))
                        c = read();
                int sgn = 1;
                if (c == '-') {
                        sgn = -1;
                        c = read();
                }
                long res = 0;
                do {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public String ns() {
                int c = read();
                while (isSpaceChar(c))
                        c = read();
                StringBuilder res = new StringBuilder();
                do {
                        res.appendCodePoint(c);
                        c = read();
                } while (!isSpaceChar(c));
                return res.toString();
        }

        public boolean isSpaceChar(int c) {
                if (filter != null)
                        return filter.isSpaceChar(c);
                return isWhitespace(c);
        }

        public boolean isWhitespace(int c) {
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private String readLine0() {
                StringBuilder buf = new StringBuilder();
                int c = read();
                while (c != '\n' && c != -1) {
                        if (c != '\r')
                                buf.appendCodePoint(c);
                        c = read();
                }
                return buf.toString();
        }

        public String readLine() {
                String s = readLine0();
                while (s.trim().length() == 0)
                        s = readLine0();
                return s;
        }

        public String readLine(boolean ignoreEmptyLines) {
                if (ignoreEmptyLines)
                        return readLine();
                else
                        return readLine0();
        }

        public BigInteger readBigInteger() {
                try {
                        return new BigInteger(ns());
                } catch (NumberFormatException e) {
                        throw new InputMismatchException();
                }
        }

        public char readCharacter() {
                int c = read();
                while (isSpaceChar(c))
                        c = read();
                return (char) c;
        }

        public double readDouble() {
                int c = read();
                while (isSpaceChar(c))
                        c = read();
                int sgn = 1;
                if (c == '-') {
                        sgn = -1;
                        c = read();
                }
                double res = 0;
                while (!isSpaceChar(c) && c != '.') {
                        if (c == 'e' || c == 'E')
                                return res * Math.pow(10, ni());
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = read();
                }
                if (c == '.') {
                        c = read();
                        double m = 1;
                        while (!isSpaceChar(c)) {
                                if (c == 'e' || c == 'E')
                                        return res * Math.pow(10, ni());
                                if (c < '0' || c > '9')
                                        throw new InputMismatchException();
                                m /= 10;
                                res += (c - '0') * m;
                                c = read();
                        }
                }
                return res * sgn;
        }

        public boolean eof() {
                int value;
                while (isSpaceChar(value = peek()) && value != -1)
                        read();
                return value == -1;
        }

        public String next() {
                return ns();
        }

        public SpaceCharFilter getFilter() {
                return filter;
        }

        public void setFilter(SpaceCharFilter filter) {
                this.filter = filter;
        }
       
    }
     public interface SpaceCharFilter {
         public boolean isSpaceChar(int ch);
     }

}

