题目描述

🐧 干旱的企鹅岛终于迎来了一场大雨！工程师们用高低错落的柱子围成储水区，现在他们想知道能蓄多少水。你能帮帮这些翘首以盼的企鹅吗？(^_^)

给定一排紧密排列的柱子高度，想象雨水会乖巧地填满所有低洼处。你的任务是计算这些柱子能接住多少雨水
（柱子宽度为 1，雨水按单位面积计算）

输入

• 第一行为整数 n，表示柱子数量(1 ≤ n ≤ 10⁵)
• 第二行为 n 个非负整数，表示各柱子高度（0 ≤ 高度 ≤ 10⁴）

输出

🪣 一个整数，表示雨水总量

样例

输入

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

输出

6

解释

样例中雨水填充效果如图，共积蓄6单位面积雨水