using System;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        int[] arr = {3,0,0,2,0,4};

        int[] arr1 = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};

        Console.WriteLine(RainWater(arr));

        Console.WriteLine(RainWater1(arr));

        Console.WriteLine(RainWater2(arr1));

    }

    private static int RainWater(int[] arr)

    {

        int rainwater = 0;

        int[] maxRight = new int[arr.Length];

        int maxSeenSoFar = 0;

        int maxSeenLeft =0;

        for(int i = arr.Length-1;i>=0 ;i--)

        {

            if ( maxSeenSoFar < arr[i] )

            {

                maxSeenSoFar = arr[i];

                maxRight[i] = maxSeenSoFar;

            }

            else

                maxRight[i] = maxSeenSoFar;

        }

        for(int i =0;i<arr.Length ;i++)

        {

            rainwater += Math.Max(Math.Min(maxSeenLeft,maxRight[i])-arr[i],0);

            if ( arr[i] > maxSeenLeft )

                maxSeenLeft = arr[i];

        }

        return rainwater;

    }

    private static int RainWater1(int[] arr)

    {

        int count = 0;

        int[] right = new int[arr.Length];

        int[] left = new int[arr.Length];

        right[arr.Length-1] = arr[arr.Length-1];

        for(int i = arr.Length-2;i>=0;i--)

        {

            right[i] = Math.Max(right[i+1],arr[i]);

        }

        left[0] = arr[0];

        for(int i=1;i<arr.Length-1;i++)

        {

            left[i] = Math.Max(left[i-1],arr[i]);

        }

        for (int i = 0; i < arr.Length; i++)

           count += Math.Min(left[i],right[i]) - arr[i];

        return count;

    }

    private static int RainWater2(int[] arr)

    {

        int result = 0;

        // maximum element on left and right

        int left_max = 0, right_max = 0;

        // indices to traverse the array

        int lo = 0, hi = arr.Length-1;

        //{3,0,0,2,0,4}

        //{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}

        while(lo <= hi) 

        {

            if(arr[lo] < arr[hi])

            {

                if(arr[lo] > left_max)

                // update max in left

                left_max = arr[lo];

                else

                // water on curr element = max - curr

                result += left_max - arr[lo];

                lo++;

            }

            else

            {

                if(arr[hi] > right_max)

                // update right maximum

                right_max = arr[hi];

                else

                result += right_max - arr[hi];

                hi--;

            }

        }

        return result;

    }

}