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


public class Project1{
  static void solutionP2(){}
   static void selectionsort(int[] a){
        int t,ind;
        for (int i = 0; i < a.length; i++) {
            ind=i;
            for (int j = i+1; j < a.length; j++) {
            if(a[j]<a[i]){ind=j;}    
            }
            t=a[ind];a[ind]=a[i];a[i]=t;
        }
        for (int i : a) {
            System.out.print(i+" ");
        }
    }
  static void solutionP1(){solutionP2();}
   static void bubblesort(int [] a){
       int t,flag;
       for (int i = 1; i < a.length; i++) {
           flag=0;
           for (int j =0; j <a.length-i; j++) {
               if(a[j]>a[j+1]){t=a[j+1];a[j+1]=a[j];a[j]=t;flag=1;}
           }
          if(flag==0)break;
       }
       for (int i :a) {
           System.out.print(i+" ");
       }
   }
   static void fun(){
       solutionP1();
   }
   static void insertionsort(int[]a){
       List<Integer>list=new ArrayList();
       list.add(0,a[0]);
       int ind=0;
       for (int i = 1; i < a.length; i++) {
         ind=0;
       
           while(a[i]>list.get(ind)&&ind<list.size()){ind++;}
           list.add(ind,a[i]);
         
       }
       System.out.println(list);
   }
 //merge sort
   
   // Merges two subarrays of arr[]. 
    // First subarray is arr[l..m] L(index) to m
    // Second subarray is arr[m+1..r] m+one to r
   static void merge(int arr[], int l, int m, int r) 
    { 
        // Find sizes of two subarrays to be merged 
        int n1 = m - l + 1; 
        int n2 = r - m; 
  
        /* Create temp arrays */
        int L[] = new int [n1]; 
        int R[] = new int [n2]; 
  
        /*Copy data to temp arrays*/
        for (int i=0; i<n1; ++i) 
            L[i] = arr[l + i]; 
        for (int j=0; j<n2; ++j) 
            R[j] = arr[m + 1+ j]; 
  
  
        /* Merge the temp arrays */
  
        // Initial indexes of first and second subarrays 
        int i = 0, j = 0; 
  
        // Initial index of merged subarry array 
        int k = l; 
        while (i < n1 && j < n2) 
        { 
            if (L[i] <= R[j]) 
            { 
                arr[k] = L[i]; 
                i++; 
            } 
            else
            { 
                arr[k] = R[j]; 
                j++; 
            } 
            k++; 
        } 
  
        /* Copy remaining elements of L[] if any */
        while (i < n1) 
        { 
            arr[k] = L[i]; 
            i++; 
            k++; 
        } 
  
        /* Copy remaining elements of R[] if any */
        while (j < n2) 
        { 
            arr[k] = R[j]; 
            j++; 
            k++; 
        } 
    } 
  
    // Main function that sorts arr[l..r] using 
    // merge() 
   static void sort(int arr[], int l, int r) 
    { 
        if (l < r) 
        { 
            // Find the middle point 
            int m = (l+r)/2; 
  
            // Sort first and second halves 
            sort(arr, l, m); 
            sort(arr , m+1, r); 
  
            // Merge the sorted halves 
            merge(arr, l, m, r); 
        } 
    } 
  
    /* A utility function to print array of size n */
    static void printArray(int arr[]) 
    { 
        int n = arr.length; 
        for (int i=0; i<n; ++i) 
            System.out.print(arr[i] + " "); 
        System.out.println(); 
    } 
  
    // Driver method 
    static int fac(int a,int b){
        int min=Math.min(a, b),min2=min-1;
        while(min2>0){min*=min2--;}
        return min;
    }
    public static void main(String[] args) {
         Scanner sc=new Scanner(System.in);
         int n=sc.nextInt(),ser=0,dim=0;sc.nextLine();
         ArrayList <Integer>a=new ArrayList();
         for (int i = 0; i < n; i++) {
            a.add(sc.nextInt());
        }
            while(a.size()!=0){
                if(a.get(0)>a.get(a.size()-1)){ser+=a.get(0);a.remove(0);}
                else{ser+=a.get(a.size()-1);a.remove(a.size()-1);}
                if(a.size()>0){
                if(a.get(0)>a.get(a.size()-1)){dim+=a.get(0);a.remove(0);}
                else{dim+=a.get(a.size()-1);a.remove(a.size()-1);}}
            }
         System.out.println(ser+" "+dim);
   }   
}