class Solution {

    int MOD = 1000000007;

    public int maxSumMinProduct(int[] nums) {

        // 子数组若最小值相等，和肯定要越大越好

        // 当前下标 i，

        //  - 需要往左边寻找第一个大于 nums [i] 的元素下标 l

        //  - 需要往右边寻找第一个大于等于 nums [i] 的元素下标 r

        // 此时对答案的贡献值为 nums [i] * sum (l, r)

        int n = nums.length;

        // 前缀和

        long[] s = new long[n + 1];

        for (int i = 0; i < n; i++) {

            s[i + 1] = s[i] + nums[i];

        }

        // 存放的是递增的元素

        Deque<Integer> st = new LinkedList<>();

        st.addFirst(-1);

        long ans = 0;

        for (int r = 0; r <= n; r++) {

            // 说明还有剩余元素，此时内部都是递增的，其右边界为 n，需要都满足条件

            int x = r == n ? -1 : nums[r];

            while (st.size() > 1 && nums[st.peekFirst()] >= x) {

                // 此时弹出的栈顶元素 poll 右边第一个小于等于 poll 的元素为 r

                Integer i = st.pollFirst();

                // 此时栈顶弹出的 poll 下面的元素正好是 poll 的左边界

                int l = st.peekFirst();

                System.out.println("l:" + l + " i:" + i + " r:" + r);

   ans = Math.max(ans, nums[i] * (s[r] - s[l + 1]));

            }

            st.addFirst(r);

        }

        return (int) (ans % MOD);

    }

}