class TrapRainWater {
 
	public static void main(String[] args) {
		int[] bars = {0, 1, 0, 2, 1, 0 , 1, 3, 2, 1, 2, 1 };
		System.out.println(trap(bars));
	}
 
	// Brute Force Approach
	static int trapWaterUsingBrute(int[] bars) {
		int len = bars.length;
		int trappedWater = 0;
		for (int i = 1; i < len - 1; i++) {
			int lmax = 0, rmax = 0;
 
			for (int j = i - 1; j >= 0; j--)
				lmax = Math.max(lmax, bars[j]);
 
			for (int j = i + 1; j < len; j++)
				rmax = Math.max(rmax, bars[j]);
 
			trappedWater += Math.max(0, Math.min(lmax, rmax) - bars[i]);
		}
		return trappedWater;
	}
}

Y2xhc3MgVHJhcFJhaW5XYXRlciB7CgoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewoJCWludFtdIGJhcnMgPSB7MCwgMSwgMCwgMiwgMSwgMCAsIDEsIDMsIDIsIDEsIDIsIDEgfTsKCQlTeXN0ZW0ub3V0LnByaW50bG4odHJhcChiYXJzKSk7Cgl9CgkKCS8vIEJydXRlIEZvcmNlIEFwcHJvYWNoCglzdGF0aWMgaW50IHRyYXBXYXRlclVzaW5nQnJ1dGUoaW50W10gYmFycykgewoJCWludCBsZW4gPSBiYXJzLmxlbmd0aDsKCQlpbnQgdHJhcHBlZFdhdGVyID0gMDsKCQlmb3IgKGludCBpID0gMTsgaSA8IGxlbiAtIDE7IGkrKykgewoJCQlpbnQgbG1heCA9IDAsIHJtYXggPSAwOwoKCQkJZm9yIChpbnQgaiA9IGkgLSAxOyBqID49IDA7IGotLSkKCQkJCWxtYXggPSBNYXRoLm1heChsbWF4LCBiYXJzW2pdKTsKCgkJCWZvciAoaW50IGogPSBpICsgMTsgaiA8IGxlbjsgaisrKQoJCQkJcm1heCA9IE1hdGgubWF4KHJtYXgsIGJhcnNbal0pOwoKCQkJdHJhcHBlZFdhdGVyICs9IE1hdGgubWF4KDAsIE1hdGgubWluKGxtYXgsIHJtYXgpIC0gYmFyc1tpXSk7CgkJfQoJCXJldHVybiB0cmFwcGVkV2F0ZXI7Cgl9Cn0=