Masala #MVDDWFG7OD

Ниже вам будет приведен псевдокод некоторой функции Foo. Вам нужно понять, как работает эта функция, и лучше ее реализовать. 

function Foo(array_of_ints a): // input parameters: array of integers
     result = 0
     while size(a) > 2: // as long as the array length is at least two elements
         sort(a) // sort the array in ascending order
         n = size(a)
         x = a[0] + a[n - 2]
         result += x // add x to the accumulated result
         delete(a, n-2) // delete element by index (n-2)
         delete(a, 0) // delete element at index 0
         add(a, x) // add element by value x to end of array
     return sum(a) + result // add the sum of elements to the accumulated result

Обратите внимание, что этот псевдокод использует 0-индексацию массива.

Первая строка входных данных содержит одно целое число \(n\) (1 ≤ \(n\) ≤ 300 000) — количество элементов в массиве \(a\).

Вторая строка содержит \(n\) целых чисел \(a_i\) (0 ≤ \(a_i\) ≤ 1 000 000). Числа в строке разделены одинарными пробелами.

Выведите одно целое число - ответ на задачу.