static class ConvexHullTrick {

        static final long NEGATIVE_INF = -100L * 1000 * 1000 * 1000;

        static class Line {
            long k, b;
            long xNumerator, xDenominator;

            public Line(long k, long b, long xNumerator, long xDenominator) {
                super();
                this.k = k;
                this.b = b;

                this.xNumerator = xNumerator;
                this.xDenominator = xDenominator;
            }

            double x() {
                return xNumerator * 1.0 / xDenominator;
            }
        }

        Line[] stack;
        int size;

        ConvexHullTrick(int size, long baseB) {
            stack = new Line[size + 10];
            size = 0;

            __insert(0, baseB, NEGATIVE_INF - 10, 1);
        }

        private void __insert(long k, long b, long xNumerator, long xDenominator) {
            stack[size++] = new Line(k, b, xNumerator, xDenominator);
        }

        void updateStack(long nextHeight) {
            while (size > 1) {
                Line lastLine = stack[size - 1];
                if (lastLine.k >= nextHeight) {
                    --size;
                    stack[size] = null;
                } else {
                    break;
                }
            }
        }

        long getBest(long x) {
            int result = 0;

            for (int left = 1, right = size - 1; left <= right; ) {
                int mid = (left + right) >> 1;
                Line line = stack[mid];

                if (line.x() <= x) {
                    result = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

            Line line = stack[result];
            return line.k * x + line.b;
        }

        void addLine(int index, long k, long b) {
            while (size > 1) {
                Line line = stack[size - 1];

                if (line.k == k) {
                    --size;
                    stack[size] = null;

                    continue;
                }

                long lastXNumerator = (b - line.b);
                long lastXDenominator = (line.k - k);

                double lastX = lastXNumerator * 1.0 / lastXDenominator;

                if (lastX > line.x()) {
                    __insert(k, b, lastXNumerator, lastXDenominator);
                    return;
                } else {
                    --size;
                    stack[size] = null;
                }
            }

            __insert(k, b, NEGATIVE_INF + index, 1);
        }
    }

    static long getAnswer(int[] a, int k) {
        IntIndexPair[] iip = IntIndexPair.from(a);
        Arrays.sort(iip, new Comparator<IntIndexPair>() {

            @Override
            public int compare(IntIndexPair a, IntIndexPair b) {
                if (a.value != b.value) {
                    return a.value - b.value;
                }

                return b.index - a.index;
            }
        });

        int n = a.length;

        int[] lefts = new int[n], rights = new int[n];

        NavigableSet<Integer> indexes = new TreeSet<Integer>();
        indexes.add(-1);
        indexes.add(n);

        for (IntIndexPair pair : iip) {
            int index = pair.index;

            int prevIndex = indexes.lower(index);
            int nextIndex = indexes.higher(index);

            lefts[index] = prevIndex;
            rights[index] = nextIndex;

            indexes.add(index);
        }

        final long NEGATIVE_INF = Long.MIN_VALUE / 3;

        long[][] dp = new long[k + 2][n + 1];

        for (long[] dp1 : dp) {
            Arrays.fill(dp1, NEGATIVE_INF);
        }

        dp[0][0] = 0;

        long answer = NEGATIVE_INF;

        ConvexHullTrick[] tricks = new ConvexHullTrick[k + 2];
        for (int j = 0; j < tricks.length; ++j) {
            tricks[j] = new ConvexHullTrick(n, dp[j][0]);
        }

        for (int i = 0; i < n; ++i) {
            int left = lefts[i];
            int right = rights[i];

            long value = a[i];
            long curSquare = (i - left) * value;

            for (int j = 1; j <= k + 1; ++j) {
                long curDp = dp[j][i + 1];

                ConvexHullTrick trick = tricks[j - 1];
                trick.updateStack(value);

                long best = trick.getBest(left);

                if (best != NEGATIVE_INF) {
                    curDp = Math.max(curDp, curSquare + best);
                }

                answer = Math.max(answer,  curDp + (right - i - 1) * value);

                dp[j][i + 1] = curDp;
            }

            for (int j = 1; j <= k + 1; ++j) {
                if (dp[j][i + 1] != NEGATIVE_INF) {
                    tricks[j].addLine(i, value, dp[j][i + 1] - value * i);
                }

            }
        }

        for (long[] dp1 : dp) {
            for (long value : dp1) {
                answer = Math.max(answer, value);
            }
        }

        return answer;
    }