排排坐

题目描述

⽼师正在和⼩朋友们分糖果。 ⼩朋友们先在⾃⼰的⼿上写⼀个数字，然后坐成⼀排。 ⽼师分发糖果的规则是：每个⼩朋友获得⾃⼰以及左侧所有⼩朋友的⼿上数字之和个糖果。 现在⼩朋友们都已经在⾃⼰⼿上写上了数字。 请帮⼩朋友们安排合适的座位顺序，使得⼩朋友们分到的糖果总量最⼤，输出这个最⼤值。

输入格式

输⼊ ⾏， 第⼀⾏为⼀个正整数 ，表⽰⼩朋友的个数； 第⼆⾏为 个正整数 ，表⽰⼩朋友们⼿上的数字，整数之间以空格分隔。

输出格式

输出⼀个整数，表⽰⼩朋友们可能分到的最⼤糖果总数量。

样例输入 #1

5
7 5 8 9 3

样例输出 #1

111

样例解释 #1

⼩朋友安排座位后从左向右每⼈⼿上数字依次是： 。 这时可以得到最多的糖果： 。

数据范围

， 。

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。