package com.demo;

import java.util.*;

public class SnowSpread {
    public static void main(String args[]) {
        int[] input = {0, 1, 3, 0, 1, 2, 0, 4, 2, 0, 3, 2, 1};
        System.out.println(solve(input));
    }

    private static int solve(int[] input) {
        PriorityQueue<AbstractMap.SimpleEntry<Integer, Integer>> heap = new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        AbstractMap.SimpleEntry<Integer, Integer> val;
        boolean[] visited = new boolean[input.length];
        int sum = 0, index, curleft = 0, curright = 0;
        for (int i = 0; i < input.length; i++) {
            heap.add(new AbstractMap.SimpleEntry<Integer, Integer>(i, input[i]));
        }
        int va11 = heap.poll().getKey();
        int va12 = heap.poll().getKey();
        int left = Math.min(va11, va12);
        int right = Math.max(va11, va12);
        int height = Math.min(input[left], input[right]);
        visited[left] = true;
        visited[right] = true;
        for (int i = left + 1; i < right; visited[i] = true, i++)
            sum += height - input[i];

        while ((val = heap.poll()) != null) {
            index = val.getKey();
            if (!visited[index]) {
                if (index > right) {
                    curleft = right;
                    curright = index;
                    right = index;
                } else if (index < left) {
                    curleft = index;
                    curright = left;
                    left = index;
                }
                visited[index] = true;
                height = Math.min(input[curleft], input[curright]);
                for (int i = curleft + 1; i < curright; visited[i] = true, i++)
                    sum += height - input[i];
            }
        }
        return sum;
    }
}