L. Самая дорогая склейка

Та же склейка куч, но найти надо наибольшую возможную суммарную стоимость.

Жадность переворачивается: каждый ход склеиваем две наибольшие кучи. Тогда крупные размеры участвуют в наибольшем числе склеек.

Проделать это стоит ровно затем, чтобы убедиться: доказательство из классной задачи работает в обе стороны. Стоимость по-прежнему равна $\sum a_i \cdot \mathrm{depth}_i$, только теперь глубину надо максимизировать, и глубже всех должны оказаться самые большие кучи.

Итоговое дерево вырождается в цепочку - как самое неудачное дерево поиска из прошлого занятия. Это не совпадение: обе задачи про то, как «жадность наоборот» загоняет структуру в вырожденный вид.

В первой строке - число $n$ ($1 \le n \le 10^5$).

Во второй - $n$ размеров куч, целых от 1 до 1000.

Одно число - наибольшая суммарная стоимость склейки.