Trapping Rain Water Problem

You are given an array of non-negative integers representing the elevation map where the width of each bar is 1. Your task is to calculate how much water can be trapped after it rains. The water trapped above index (i) is determined by the formula: [ \text{water}_i = \min(\text{leftMax}_i,,\text{rightMax}_i) - \text{height}_i, ] where (\text{leftMax}_i) is the maximum height of a building to the left of index (i) (inclusive), and (\text{rightMax}_i) is the maximum height to the right of index (i) (inclusive). Sum these values over all indices to get the total trapped water. This problem is a classic application of dynamic programming and two-pointer techniques.

inputFormat

The input consists of a single line containing zero or more space-separated integers. Each integer represents the height of a building. An empty input indicates no buildings.

outputFormat

Output a single integer representing the total units of water trapped.## sample

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

6