/*  merge2
問題描述：
見merge2.pdf

算法設計：
1、先將輸入的數組a[0:n-1]采用快速排序方法進行降序排列（n為數組長度）
2、取得最后兩位進行相加，將結果sum累加至變量counter中
3、數組長度減少1，且末元素的值變為sum
4、對新的數組按照大小進行遞減排序（只需對sum進行排序即可）
5、如果n>=2，則重復步驟2至步驟4
6、如果n<2，則程序結束，counter的值即為最終解，將其輸入到output.txt文件中
*/
#include <stdlib.h>
#include <fstream.h>

ofstream out("output.txt");//創建輸出文件

//交換數組中2元素的函數
void swap(int a[],int i,int j);

//對數組進行劃分的函數，返回一個基準元素x，數組a[]中比x小的移動到x右邊，比x大的移動到x左邊
//參數1：要排序的數組
//參數2：起始元素下標
//參數3：結束元素下標
int partition(int a[],int p,int r);

//快速排序算法（排序結果為遞減順序）
//參數1：要排序的數組
//參數2：起始元素下標
//參數3：結束元素下標
void quickSortDesc(int a[],int p,int r);

//對數組a重新進行降序排列（只對最后一個元素進行插入排序）
void reSortDesc(int a[],int n);

//計算將n堆石子合并成一堆的最小總費用的函數，返回值即為最終解
int merge2(int a[],int n);

//主函數
int main(){
	ifstream fin("input.txt",ios::nocreate);//打開輸入文件
	int n;//數組長度

	if(!fin){
		cerr<<"the input file is not exist!"<<endl;
		return -1;
	}
	else{
		fin>>n;
	}

	int *a;
	a = new int[n];
	int i;
	//讀入數據
	for(i=0;i<n;i++){
		fin>>a[i];
	}

	quickSortDesc(a,0,n-1);//對數組進行降序排列
	
	int mixFee = merge2(a,n);//計算最小總費用

	out<<mixFee;//將結果輸出到output.txt文件

	delete[] a;

	fin.close();
	out.close();

	return 0;
}

void swap(int a[],int i,int j){
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

void quickSortDesc(int a[],int p,int r){
	if(p<r){
		int q = partition(a,p,r);
		quickSortDesc(a,p,q-1);
		quickSortDesc(a,q+1,r);
	}
}

int partition(int a[],int p,int r){
	int i = p;
	int j = r+1;

	int x = a[p];

	while(true){
		while(a[++i]>x);
		while(a[--j]<x);

		if(i>=j)break;
		swap(a,i,j);
	}

	a[p] = a[j];
	a[j] = x;

	return j;
}

int merge2(int a[],int n){
	int counter = 0;
	int len = n;
	
	if(n>=2){
		counter = a[n-1]+a[n-2];
		
		a[n-2] = counter;

		reSortDesc(a,n-1);//對新數組重新進行降序排序

		counter += merge2(a,n-1);//遞歸調用
	}
	else{
		return 0;
	}

	return counter;
}

void reSortDesc(int a[],int n){
	int temp = a[n-1];
	int i = n-2;
	while(i>=0){
		if(temp>a[i]){
			a[i+1] = a[i];
			if(i==0){
				a[i] = temp;
			}
		}
		else{
			a[i+1] = temp;
			break;
		}
		i--;
	}
}