C0737 排排坐
排排坐
题目描述
老师正在和小朋友们分糖果。小朋友们先在自己的手上写一个数字，然后坐成一排。老师分发糖果的规则是：每个小朋友获得自己以及左侧所有小朋友的手上数字之和个糖果。
现在小朋友们都已经在自己手上写上了数字。请帮小朋友们安排合适的座位顺序，使得小朋友们分到的糖果总量最大，输出这个最大值。
输入
输入 2 行，
第一行为一个正整数 n，表示小朋友的个数；
第二行为 n 个正整数 a1,a2,...,an，表示小朋友们手上的数字，整数之间以空格分隔。
输出
输出一个整数，表示小朋友们可能分到的最大糖果总数量。
数据范围
1≤n≤1000，1≤ai≤1000.
输入样例1
5
7 5 8 9 3
输出样例1
111