using System;

using System.Collections.Generic;

using System.Collections;

public class Program

{

    public static void Main()

    {

        List<int> pw = new List<int>() {20,13,8,9};

        long a = getHeaviestPackage(pw);

        Console.WriteLine(a);

        List<int> pw1 = new List<int>() {1,2,3};

        long a1 = getTotalImbalance(pw1);

        Console.WriteLine(a1);

    }

    public static long getHeaviestPackage(List<int> packageWeights) {

//use a stack to complete the combine process

        Stack<long> stack = new Stack<long>();

        long res = 0;

        for (int i = packageWeights.Count - 1; i >= 0; i--) {

        long cur = packageWeights[i];

        //try to combine as many as possible

        while ((stack.Count != 0) && cur < stack.Peek()) {

        cur += stack.Pop();

        }

        stack.Push(cur);

        }

        //find the heaviest package available

        while (stack.Count != 0) {

        res = Math.Max(res, stack.Pop());

        }

        return res;

        }

    public static long getTotalImbalance(List<int> weight) {

        // Write your code here

        Stack<int> stack = new Stack<int>();

        long res = 0;

        //calculate for all the mins among all the possible subarrays; cur is

​

        for (int i = 0; i <= weight.Count; i++) {

        while ((stack.Count != 0) && (i == weight.Count || weight[(stack.Peek())] > weight[i])) {

        int cur = stack.Pop();

        int leftB = (stack.Count == 0) ? -1 : stack.Peek();

        res -= (long) (i - cur) * (cur - leftB) * weight[cur];

        }

        stack.Push(i);

        }

        stack.Clear();

​

        for (int i = 0; i <= weight.Count; i++) {

        while ((stack.Count != 0) && (i == weight.Count || weight[(stack.Peek())] < weight[i])) {

        int cur = stack.Pop();

        int leftB = (stack.Count == 0) ? -1 : stack.Peek();

        res += (long) (i - cur) * (cur - leftB) * weight[cur];

        }

        stack.Push(i);

        }

        return res;

    }

}