class Solution {
    public int trap(int[] height) {
        if(height.length <= 1 ){
            return 0;
        }
        int left = 0,right = 0;
        for (int i = 0; i < height.length; i++) {
            if(height[i] > height[left]){
                left = i;
            }
        }
        for (int i = 0; i < height.length; i++) {
            if(height[i] > height[right] && i != left){
                right = i;
            }

        }
        if(left > right){
            right = left + right;
            left = right - left;
            right = right - left;
        }
        return add(left,right,height)+leftsum(0,left,height)+rightsum(right,height.length-1,height);

    }
    public int leftsum(int left,int right,int[] height){
        if(left+1 >= right){
            return 0;
        }
        int index = 0;
        for(int i = 0;i < right;i++){
            if(height[index] < height[i]){
                index = i;
            }
        }
        return add(index,right,height)+leftsum(0,index,height);
    }
    public int rightsum(int left,int right,int[] height){
        if(left+1 >= right){
            return 0;
        }
        int index = left+1;
        for(int i = left+1;i < height.length;i++){
            if(height[index] < height[i]){
                index = i;
            }
        }
        return add(left,index,height)+rightsum(index,right,height);
    }
    public int add(int left,int right,int[] height){
        if(left + 1 >= right){
            return 0;
        }
        int min = Math.min(height[left],height[right]);
        if(min == 0){
            return 0;
        }
        int sum = 0;
        for(int i = left + 1;i < right;i++){
            sum += min - height[i];
        }
        return sum;
    }
}

class Trie {
    HashSet<String> set = new HashSet<>();
    public Trie() {

    }
    public void insert(String word) {
        set.add(word);
    }
    public boolean search(String word) {
        return set.contains(word);
    }
    public boolean startsWith(String prefix) {
        for (String s : set) {
            if(s.startsWith(prefix)) return true;
        }
        return false;
    }
}

class StockSpanner {

    public StockSpanner() {
    }
    
    // 初始化下标
    int index = 0;
    // 存放下标
    Deque<Integer> deque = new LinkedList<>();
    // 存放值
    Deque<Integer> all = new LinkedList<>();

    public int next(int price) {
        // 如果 all 为空或者 price 小于栈顶，入栈 ，返回 1
        if(all.isEmpty() || price < all.peek()) {
            all.push(price);
            deque.push(index++);
            return 1;
        }
        // 如果 price >= 栈顶，出栈，直到小于等于栈顶，入栈，返回下标之差
        else {
            int res = 0;
            int i = 0;
            while (!all.isEmpty() && price >= all.peek()){
                i = deque.pop();
                all.pop();
            }
            res = deque.isEmpty() ? index + 1 : index - deque.peek();
            all.push(price);
            deque.push(index++);
            return res;
        }
    }
}