Trapping Rainwater :
Difficulty Level : Medium
Submissions : 274
Asked In :
Marks :10
: 5 | : 0
You ar given an array $$$a$$$ consisting of $$$n$$$ integers representing the height map where the width of each bar is $$$1$$$ unit. If $$$a_i=k$$$, this implies that the height of the $$$i^{th}$$$ bar extending from $$$x=i$$$ to $$$x=i+1$$$ is $$$k$$$. Rainwater gets trapped between these bars when it rains. Find how many units of water will get trapped when it rains.
Input
The first line contains a single integer $$$n(1 \leq n \leq 2 \times 10^5)$$$. The next line contains $$$n$$$ spaces integers $$$a_1,a_2,...,a_n(0 \leq a_i \leq 10^6)$$$.
Output
Output a single integer - the amount of water that can be trapped when it rains.
Example
Input
6 5 0 3 5 9 1
Output
7
