Дано масив з \(n\) чисел, ваше завдання полягає в тому, щоб розділити його на \(n\) підмасивів, кожен з яких має один елемент.

Під час кожного ходу ви можете вибрати будь-який підмасив і розділити його на два підмасиви. Вартість такого переміщення є сумою значень у вибраному підмасиві.

Яка мінімальна загальна вартість, якщо діяти оптимально?

Обмеження

• \(1≤n≤5000\)
• \(1≤x_i ​ ≤10^9\)

Формат вхідних даних

У першому рядку вхідних даних є ціле число \(n\): розмір масиву. Елементи масиву пронумеровані \(1,2,…,n\).

У другому рядку міститься \(n\) цілих чисел \(x_1 ​ ,x_2 ​ ,…,x_n\) ​ : елементи масиву.

Формат вихідних даних

Вивести одне ціле число: мінімальна загальна вартість.

Приклад вхідних даних

5
2 7 3 2 5

Приклад вихідних даних

43