题目内容

一条路高低不平，下雨时水会留在低洼的地方。

把路面简化成一个直线，用一个数组描述它的高低。

比如[3 2 4]代表一条$3$个单位长的路，高度依次为3 2 4，则下雨时，它的最大积水可以达到$1$。

实际一个计算最大积水的 函数，输入是代表描述路面高低的数组，输出是最大积水量

输入描述

第一行给出一个整数$n$代表数组长度$(1<=n<=1e5)$ 接下来一行n个数表示路面road数组$(1<=road_i<=10^9)$

输出描述

输出一个整数代表最大积水量

样例1

输入

3
3 2 4

输出

1

说明

样例2

输入

3
3 2 1

输出

0

说明