import java.util.Stack;

public class TrappingRainWater {
	  public int trap(int[] height) {
	        int left = 0;
	        int right = height.length - 1;
	        int res = 0;
	        int leftMax = 0;
	        int rightMax = 0;
	        while (left < right) {
	            if (height[left] < height[right]) {
	                leftMax = Math.max(height[left], leftMax);
	                res += leftMax - height[left];
	                left++;
	            } else {
	                rightMax = Math.max(height[right], rightMax);
	                res += rightMax - height[right];
	                right--;
	            }
	        }
	        return res;
	    }
	  public int trap1(int[] A) {
	        if (A==null) return 0;
	        Stack<Integer> s = new Stack<Integer>();
	        int i = 0, maxWater = 0, maxBotWater = 0;
	        while (i < A.length){
	            if (s.isEmpty() || A[i]<=A[s.peek()]){
	                s.push(i++);
	            }
	            else {
	                int bot = s.pop();
	                maxBotWater = s.isEmpty()? // empty means no il
	                0:(Math.min(A[s.peek()],A[i])-A[bot])*(i-s.peek()-1);
	                maxWater += maxBotWater;
	            }
	        }
	        return maxWater;
	    }
	
	    public static void main(String[] args) {
			// TODO Auto-generated method stub
	    	int s[]= {0,1,0,2,1,0,1,3,2,1,2,1};
	    	int num1[]= {2,1,0,3,0,0,4};
	    	int n=new TrappingRainWater().trap1(num1);
	    	System.out.println(n);
		}
}