Trapping Rain Water

Given an array representing the height of pillars, compute the maximum amount of water that can be trapped between these pillars after it rains. The water trapped above a pillar is determined by the smaller of the highest pillars on its left and right sides. Formally, if we denote by (L_i) the maximum height to the left of index (i) and by (R_i) the maximum height to the right, then the water trapped at index (i) is given by (\max(0, \min(L_i, R_i) - h_i)), where (h_i) is the height at index (i). Your task is to compute the total amount of water trapped across all the pillars.

inputFormat

The first line contains an integer (n) which denotes the number of pillars. The second line contains (n) space-separated integers representing the heights of the pillars.

outputFormat

Output a single integer which is the maximum amount of water that can be trapped.## sample

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

6