package com.mgtriffid.misc;

import java.util.Map;
import java.util.TreeMap;

public class Compartment {

    public int volume(int[] landscape) {
        TreeMap<Integer, Height> heightMap = new TreeMap<>();
        for (int i = 0, l = landscape.length; i < l; i++) {
            if (!heightMap.containsKey(landscape[i])) {
                heightMap.put(landscape[i], new Height(i, i, 1));
            } else {
                final Height height = heightMap.get(landscape[i]);
                height.area++;
                height.max = i;
            }
        }
        int volume = 0;
        while (heightMap.size() > 1) {
            final Map.Entry<Integer, Height> highest = heightMap.pollLastEntry();
            Height height = highest.getValue();
            Map.Entry<Integer, Height> nextTallest = heightMap.lastEntry();
            volume += (height.max - height.min - height.area + 1) * (highest.getKey() - nextTallest.getKey());
            final Height next = nextTallest.getValue();
            next.area += height.area;
            next.min = Math.min(height.min, next.min);
            next.max = Math.max(height.max, next.max);
        }
        return volume;
    }

    static class Height {
        int min, max, area;
        Height(int min, int max, int area) {
            this.min = min;
            this.max = max;
            this.area = area;
        }
    }
}