Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The idea of Huffman coding is quite simple: encode frequently used symbols with fewer bits. Huffman code is produced from the Huffman tree, which is a binary tree.Initially, we extract the frequency $($occurrence count$)$ of each symbol from the text file. In each step, we merge two sub$-$trees of the least frequency into a new binary tree, until the final binary tree is constructed. For each symbol, its Huffman code is the path from the root to the symbol node where we encode left$-$tree as $0$ and right$-$tree as $1.$ Here is an example of constructing Huffman tree:In this question, given the frequency of each symbol, can you calculate the total weighted length of the Huffman code of all symbols? For example the weighted length of the above Huffman tree is: $15\backslash$times $1+7\backslash$times $3+6\backslash$times $3+6\backslash$times $3+5\backslash$times $3=87$Well, the Huffman tree might not be unique when more than two symbols have the same frequency. However, the weighted length is always the same. In the example of four symbols with frequencies $\{3,4,7,7\},$ two possible Huffman trees could be constructed as follows:InputThe input contains multiple test cases. Each test case begins with one integer n $(0$ n $100000),$ indicating the number of symbols. The following line gives positive integers $1,2,...,$ representing the frequency of each symbol where $11000.$OutputFor each test case, print the total weighted length of the Huffman codes in a separate line.Sample input$5157665434776865543108173694233$Sample output$874279144$