U88309 聪明的小偷

从前有一个收藏家收藏了许多相同的硬币，并且将它们放在了$n$个排成一排的口袋里，每个口袋里都装了一定数量的硬币。 这些硬币价值不菲，自然引起不少人觊$(ji,4)$觎$(yu,2)$，于是收藏家每天都会来检查一次这$n$个口袋，首先他会先检查每个口袋是不是都有硬币，之后他会计算出第$1$个和第$2$个口袋的硬币数量之和，第$2$个与第$3$个口袋的硬币数量和，如此直到第$n-1$个与第$n$个口袋的硬币数量之和，得到$n-1$个数的序列。 如果收藏家发现某个口袋没有硬币，或者他计算得到的序列较上一天相比有变动，那么收藏家就知道肯定有人动了他的硬币。 有一个聪明的小偷，他想在收藏家不知道的情况下偷走一些硬币，为此，他不仅可以偷偷地从某个口袋中拿出一些硬币，也可以将硬币在口袋间任意移动，现在他想知道对于给定的$n$个口袋及对应的硬币数量，他最多能拿多少枚硬币。 小偷是很聪明的，他早就算出来啦，但是他想考考作为徒弟的你……

第一行一个正整数$n$，表示口袋的个数。 接下来一行$n$个正整数，第$i$个正整数表示第$i$个口袋里装的硬币数量。

一行一个正整数，表示答案。

【样例解释】 第一个样例中，小偷无法在收藏家不知道的情况下移动硬币。 第二个样例中，尽管小偷可以移动硬币，比如移动成3 3 7 7，但是他仍然无法拿出硬币。 第三个样例中，小偷将1,5口袋的一个硬币移动到2,4口袋中，并在口袋3中拿出一个硬币即可。 对于$50\%$的数据，有$2 \le n \le 20$，每个口袋中硬币数量$\le20$。 对于$100\%$的数据，有$2 \le n \le 999$，每个口袋中硬币数量$\le 10000$且为正整数。