腚的魔盒

时间限制:1s

空间限制:256MB

题目描述

你有一个好朋友叫腚，他在圣诞节送了你一个魔盒，魔盒的形状非常奇怪，由一个个柱子拼接而成，柱子下面有底座，所以不存在漏水的情况。下图是魔盒的截面图：

你带着魔盒很开心的回家了，但是你不小心把他掉在了马路上，结果天上下起了大雨，等你找到它的时候，魔盒里装满了雨水。你很害怕被腚发现，但是腚还是发现了。只有你算出魔盒里雨水的体积，腚才会原谅你。

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

输出一个整数，表示雨水的体积。

输入输出样例

输入 #1

12
0 1 0 2 1 0 1 3 2 1 2 1

输出 #1

6

解释 #1

上图是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

输入 #2

6
4 2 0 3 2 5

输出 #2

9

数据范围

$1\leq n \leq 10^5,0\leq a_i \leq 10^5$