题目描述

ty初一二班有一个数学天才程序龙！程序龙经常口算出很难的数学题，搞得大家都十分的崇拜他！

数学老师想要计算一下程序龙的智商，于是出了一道很难的题：数学老师给出 N 个整数，让程序龙分组。要求必须从第一个数开始分组，并且每组必须是连续的一段数，每组的数字个数不一定相同，但是要求每组和相等，程序龙需要求出每组和最小可以是多少。（当然这些数一定可以被分组，大不了直接分成一组。）

只需1秒钟，程序龙就说出了他的答案！打了数学老师一个措手不及，于是数学老师请你用计算机算出答案。

输入格式

第一行为一个数 N；

第二行为 N 个整数（每个数均小于等于 1000 ），两个数间用空格隔开。

输出格式

一行，最小的和

数据范围

$1\leq n\leq 1000000$。

样例数据

输入:

6
2 5 1 3 3 7

输出:

7

解释:

分成三组 (2，5)(1，3，3)(7) 和为 7，不存在比 7 更小的和。

输入:

6
1 1 2 3 2 3

输出:

12