/****************************************
* Section : 15
* Machine No. : N
* Roll No. : 19CS100XY
* Name : Aritra Hazra
* Assignment No : 4B
* Description : Trapping Rain Water
****************************************/

#include <stdio.h>
#define MAX 1000000

int main( )
{
    int n, i, elv[MAX], left, right, leftMax, rightMax, trap, max, j;

    /* taking an integer array of inputs */
    printf("Enter Total Width of the Cityscape: ");
    scanf("%d", &n);
    printf("Enter %d Positive Height for Elevation Map: ", n);
    for (i=0; i<n; i++)
        scanf("%d", &elv[i]);
    
    /* computing the maximum height */
    max = elv[0];
    for (i=0; i<n; i++) {
        if (elv[i] > max)
            max = elv[i];
    }    
    /* printing the elevation map */
    printf("\nThe Elevation Map:\n");
    for (i=0; i<n; i++) 
        printf("---");
    printf("\n");
    for (j=max; j>0; j--) {
        for (i=0; i<n; i++) {
            if (j > elv[i]) /* printing space for shorter buildings */
                printf("   ");
            else /* printing the building floors */
                printf("|H|");
        }
        printf("\n");
    }
    for (i=0; i<n; i++) 
        printf("---");
    printf("\n");
    for (i=0; i<n; i++) 
        printf("%2d ", elv[i]);
    printf("\n");
    for (i=0; i<n; i++) 
        printf("---");
    printf("\n");
    
    /* traversing two index pointers from left and right sides */
    left = 0; right = n-1; leftMax = 0; rightMax = 0; trap = 0;
    while (left < right) {
        if (elv[left] < elv[right]) { /* height of left is smaller than height of right */
            if (elv[left] >= leftMax) /* new maximum for left */
                leftMax = elv[left];
            else /* update trapped water with added units from left side */
                trap = trap + (leftMax - elv[left]);
            left ++;
        }
        else {
            if (elv[right] >= rightMax) /* new maximum for right */
                rightMax = elv[right];
            else /* update trapped water with added units from right side */
                trap = trap + (rightMax - elv[right]);
            right --;
        }
    }
    
    printf("\nAmount of Trapped Rain Water = %d units\n\n", trap);

    return 0;
}