说明

给定一个正整数序列a(1)，a(2)，...，a(n)，不改变序列中每个元素在序列中的位置，把它们相加，并用括号记每次加法所得的和，称为中间和。

输入格式

第一行只有一个正整数：n，第二行共有n个不超过100的正整数，数与数之间用空格隔开。 1  < =  n  < =  100

输出格式

只有一行且只有一个数据：最小的中间和

样例

4
4 1 2 3 

19