Mdd的异世界

题目描述

mdd现在在一个异世界，这个异世界仅仅只有两个维度，可以把这个世界看成一个处在一条直线上的世界。这个世界上有很多长方形的巨石，一天，这个世界下雨了，mdd想知道这些巨石之间能存多少水呢。

输入

多组输入数据

第一行一个数n，0 <= n <= 1000。

接下来n个数，代表这些巨石的高度h，h >= 0，巨石的宽度都为1。

输出

对于每组数据，输出一行，蓄水的最大值。

输入样例

3
1 0 1
4
3 1 2 3

输出样例

1
3

Hint

第一组样例代表的是一组成凹字形的巨石阵|_|，中间凹下去的既是可以蓄水的部分。