十月，东方博宜农场迎来了大丰收，农夫小胡看着一车饱满的玉米，一脸欣喜。于是把这些完全一样的玉米，分别放在 n 个排成一排的口袋中，每个袋子里都放了一定数量的玉米。这些玉米引来了博宜山小猴的觊觎，怕被偷的小胡只好每天来检查这些口袋。
为了节约时间，首先他会检查口袋里是不是还有玉米，然后计算相邻两个口袋玉米的数量和（第 1 和 第 2个口袋的数量和，第 2 和 第 3 个口袋的数量和，如此直到第 n-1 和 第 n 个口袋的数量和）,得到 n-1 个数的序列。
如果小胡发现某个口袋中没有了玉米，或者计算出的数字序列和昨天有变动，小胡就能发现猴子们偷了他的玉米。
但是博宜山有一只特别聪明的博宜猴，想在不让小胡知道的情况下偷走一些玉米。为此，身手矫健的小猴可以偷偷从口袋中拿出一些玉米，也可以把玉米在口袋间进行转移。
现在小猴已经侦查好了这 n 个口袋，以及对应的每个口袋的玉米数量，他想知道他最多能偷走多少根玉米。
第一行有一个正整数 n ，表示口袋的数量。
接下来一行有 n 个正整数，第 i 个正整数表示第 i 个口袋里装的玉米的数量。
一个非负整数，表示小猴能偷走的玉米数量
3 1 2 3
0
4 2 4 6 8
0
5 2 3 4 5 6
1
【样例解释】
第一个样例中，小猴无法在小胡不知道的情况下移动玉米。
第二个样例中，尽管小猴可以移动玉米，比如移动成3 3 7 7，但是他仍然无法拿走玉米。
第三个样例中，小猴将1,5口袋的一根玉米移动到2,4口袋中，并在口袋3中拿出一个玉米即可。
【数据规模与约定】
对于30\%的数据，有 n \leq 4
对于60\%的数据，有 2 \leq n \leq 50，每个口袋中玉米数量 \leq 20。
对于100\%的数据，有 2 \leq n \leq 999，每个口袋中玉米数量 \leq 10000 且为正整数。