from time import clock
import sys

def sort(data):
    i = 1
    while i < len(data):
        key = data[i]
        j = i - 1
        while j >= 0 and key < data[j]:
                data[j + 1] = data[j]
                j -= 1
        data[j + 1] = key
        i += 1
        
def main():
    start = clock()
    fin=open("in12_8.txt","r")
    fout=open("out_28_12_8.txt","w")
    arr=[]
    for x in fin.readlines():
            arr.append(int(x))
    n=arr[0]
    arr=arr[1:]
    sort(arr)
    l=[]
    fout.write("Optimal merge pattern is:\n")
    while(n>1):
        l.append(str(arr[0])+","+str(arr[1]))
        arr[1]=arr[0]+arr[1]
        arr=arr[1:]
        sort(arr)
        n=n-1
    l.append(str(arr[0]))
    fout.write("\n".join(l))
    end = clock()
    time= end - start
    fout.write("\n")
    fout.write("\n Total execuion time ="+ str(time)+ " seconds")
    m=sys.getsizeof(arr)+sys.getsizeof(x)+sys.getsizeof(l)+sys.getsizeof(fin)+sys.getsizeof(fout)
    fout.write("\n Memory used= "+str(m)+" bytes")
    fin.close()
    fout.close()
main()