Description
给定一个正整数序列a1,a2,…,an，不改变序列中的每个元素在序列中的位置，把它们相加，并用括号记每次加法所得的和，称为中间和。
编程：找到一种方法，添上n-1对括号，加法运算依括号顺序进行，得到n-2个中间和，使得求出使中间和最少。
例如给出的序列是4，1，2，3。
第一种添加括号方法：
（（4＋1）＋（2＋3））＝（（5）＋（5））＝（10），有三个中间和是5,5，10，它们之和为5＋5＋10＝20；
第二种添括号方法：
（4＋（（1＋2）＋3））＝（4＋（（3）＋3）＝（4＋（6））＝（10），中间和是3,6，10，它们之和为19。
Input
第一行为N，第二行依次为a1,a2,…,an（均为不大于1000的整数）。