题目描述
从前有一个收藏家收藏了许多相同的硬币，并且将它们放在了n个排成一排的口袋里，每个口袋里都装了一定数量的硬币。
这些硬币价值不菲，自然引起不少人觊觎，于是收藏家每天都会来检查一次这n个口袋，首先他会先检查每个口袋是不是都有硬币，之后他会计算出第1个和第2个口袋的硬币数量之和，第2个与第3个口袋的硬币数量和，如此直到第n-1个与第n个口袋的硬币数量之和，得到n-1个数的序列。
如果收藏家发现某个口袋没有硬币，或者他计算得到的序列较上一天相比有变动，那么收藏家就知道肯定有人动了他的硬币。
有一个聪明的小偷，他想在收藏家不知道的情况下偷走一些硬币，为此，他不仅可以偷偷地从某个口袋中拿出一些硬币，也可以将硬币在口袋间任意移动，现在他想知道对于给定的n个口袋及对应的硬币数量，他最多能拿多少枚硬币。
输入
第一行一个正整数n，表示口袋的个数。
接下来一行n个正整数，第i个正整数表示第i个口袋里装的硬币数量。
输出
样例输入输出
提示
【样例解释】
第一个样例中，小偷无法在收藏家不知道的情况下移动硬币。
第二个样例中，尽管小偷可以移动硬币，比如移动成3 3 7 7，但是他仍然无法拿出硬币。
第三个样例中，小偷将1,5口袋的一个硬币移动到2,4口袋中，并在口袋3中拿出一个硬币即可。
【数据规模与约定】
对于30%的数据，有n≤4
对于60%的数据，有2≤n≤50，每个口袋中硬币数量≤20。
对于100%的数据，有2≤n≤999，每个口袋中硬币数量≤10000且为正整数。