Ivan has n different boxes. The first of them contains some balls of n different colors.

Ivan wants to play a strange game. He wants to distribute the balls into boxes in such a way that for every i (1 ≤ i ≤ n) i-th box will contain all balls with color i.

In order to do this, Ivan will make some turns. Each turn he does the following:

  1. Ivan chooses any non-empty box and takes all balls from this box; 
  2. Then Ivan chooses any k empty boxes (the box from the first step becomes empty, and Ivan is allowed to choose it), separates the balls he took on the previous step into k non-empty groups and puts each group into one of the boxes. He should put each group into a separate box. He can choose either k = 2 or k = 3. 



The penalty of the turn is the number of balls Ivan takes from the box during the first step of the turn. And penalty of the game is the total penalty of turns made by Ivan until he distributes all balls to corresponding boxes.

Help Ivan to determine the minimum possible penalty of the game!

Input

The first line contains one integer number n (1 ≤ n ≤ 200000) — the number of boxes and colors.

The second line contains n integer numbers a1, a2, ..., an (1 ≤ ai ≤ 109), where ai is the number of balls with color i.

Output

Print one number — the minimum possible penalty of the game.

Examples

Input

3
1 2 3


Output

6


Input

4
2 3 4 5


Output

19

Note

In the first example you take all the balls from the first box, choose k = 3 and sort all colors to corresponding boxes. Penalty is 6.

In the second example you make two turns: 

  1. Take all the balls from the first box, choose k = 3, put balls of color 3 to the third box, of color 4 — to the fourth box and the rest put back into the first box. Penalty is 14; 
  2. Take all the balls from the first box, choose k = 2, put balls of color 1 to the first box, of color 2 — to the second box. Penalty is 5. 



Total penalty is 19.



// n boxes, n colors of balls, each color may have 1 to 10^9 balls

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import static java.lang.System.out;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


// initially all boxes in 1 box, goal is to group balls per color 
// each move pick all balls in 1 box and distrubute to k boxes, k=2 or 3
// pentalty is the balls on each move
// output minimal total penalty
public class BoxBalls {
    
    //SortedList sorted = new SortedList(false, 200000);//1 ≤ n ≤ 200000
    PriorityQueue<Long> pq = new PriorityQueue<>();
    BoxBalls(int []a)
    {
        for (int i:a)
            pq.add((Long)(long)i);
        long penalty=0;
        while (pq.size()>1) {
            //out.println(pq.toString());
            //long subtotal = sorted.get(0)+sorted.get(1);
            //int rem = 2;
            long subtotal =pq.poll();
            subtotal += pq.poll();
            if (pq.size()%2==1) {
                subtotal += pq.poll();//sorted.get(2);
                //rem++;
            }
            //sorted.removeAll(rem);
            pq.add(subtotal);
            //out.println("sub :"+subtotal);
            penalty += subtotal;
        }
        out.println(penalty);
    }
    public static  void test()
    {
        new BoxBalls(new int[]{1, 2, 3});           // 6
        new BoxBalls(new int[]{2, 3, 4, 5});        //19
        new BoxBalls(new int[]{1,2, 3, 4, 5, 6});   //34
    }
    public static void main(String[] args)
    {      
        judge();
    }
    public static  void judge()
    { 
        MyScanner sc=new MyScanner();
        new BoxBalls(sc.ria(sc.ni()));
    }
}

class SortedList
{
    private List<Long> ls;
    Comparator<Long> cmp;
    public SortedList(boolean reverseOrder, int capacity)
    {
        if (reverseOrder)
            cmp = Comparator.reverseOrder();
        else
            cmp = Comparator.naturalOrder();
        ls = new ArrayList<>(capacity);
    }
    public boolean add(long e)
    {
        int i=Collections.binarySearch(ls, e, cmp);
        if (i<0)
            i=-(i+1);
        ls.add(i, e);
        return true;
    }
    public long peek()
    {
        return ls.get(0);
    }
    
    public boolean remove(long e)
    {
        int i=Collections.binarySearch(ls, e, cmp);
        if (i>=0) {
            ls.remove(i);
            return true;
        }
        return false;
    }
    public boolean removeAll(int count) {
        while (count-->0) {
            ls.remove(0);
        }
        return true;
    }
    public long get(int i) {
        return ls.get(i);
    }
    public int size() {
        return ls.size();
    }
}
class MyScanner {
    BufferedReader br;
    StringTokenizer st;

    public MyScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

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

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

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

    String nextLine(){
        String str = "";
        try {
           str = br.readLine();
        } catch (IOException e) {
           e.printStackTrace();
        }
        return str;
    }
    
    public int ni()
    {
        return nextInt();
    }     
    public long nl()
    {
        return nextLong();
    }   
    public int[] ria(int N) { // read int array
        int L[]=new int[N];
        for (int i=0; i<N; i++)
            L[i]=nextInt();
        return L;
    }
    public long[] rla(int N) { // read long array
        long L[]=new long[N];
        for (int i=0; i<N; i++)
            L[i]=nextLong();
        return L;
    }
}