<?php

function trappingRainWater($arr) {
    $n = count($arr);
    $water = 0;

    // $left[i] menyimpan nilai maksimum
    // dari array
    $left = [0];

    // proses array dari kiri ke kanan
    // dari current bar
    for ($i = 1; $i < $n - 1; $i++) {
        $left[$i] = max($left[$i - 1], $arr[$i - 1]);
    }

    // $right menyimpan tinggi max ke kanan
    // dari current bar
    $right = 0;

    // process perhitungan dari kanan ke kiri
    for ($i = $n - 2; $i >= 1; $i--) {
        $right = max($right, $arr[$i + 1]);

        // cek kemungkinan untuk menampung air pada current bar
        if (min($left[$i], $right) > $arr[$i]) {
            $water += min($left[$i], $right) - $arr[$i];
        }
    }

    return $water;
}

// Main
$arr = [];
echo implode(',', $arr) . ' = ' . trappingRainWater($arr);
echo "\n";

$arr = [0,1,0];
echo implode(',', $arr) . ' = ' . trappingRainWater($arr);
echo "\n";

$arr = [2,1,3];
echo implode(',', $arr) . ' = ' . trappingRainWater($arr);
echo "\n";

$arr = [0,1,0,2,1,0,1,3,2,1,2,1];
echo implode(',', $arr) . ' = ' . trappingRainWater($arr);
echo "\n";

$arr = [2,1,0,2,1,0,1,3,5,1,3,10];
echo implode(',', $arr) . ' = ' . trappingRainWater($arr);
echo "\n";

$arr = [12,1,0,2,1,0,1,3,5,1,3,10];
echo implode(',', $arr) . ' = ' . trappingRainWater($arr);
echo "\n";