The objective is to evaluate the following double summation for a sequence $A$ of length $N$: $$ \sum_{L=0}^{N-1} \sum_{R=L}^{N-1} \left( \max_{k \in [L, R]} A[k] - \min_{k \in [L, R]} A[k] \right) $$ A brute-force enumeration of all contiguous segments results in quadratic or cubic complexity, which is insufficient for large inputs. Two linear-time strategies utilizing monotonic stacks can resolve this efficiently.

Strategy 1: Incremental Dynamic Programming

Rather than iterating over subarray boundaries, track the cumulative maximum and minimum values for all subarrays terminating at index $i$. Define $DP_{max}[i]$ as the sum of maximums for subarrays $A[0..i], A[1..i], \dots, A[i..i]$. Similarly, define $DP_{min}[i]$ for minimums. The final result becomes $\sum_{i=0}^{N-1} (DP_{max}[i] - DP_{min}[i])$.

To derive $DP_{max}[i]$, identify the nearest index $P < i$ where $A[P] > A[i]$. For any starting position $k$ satisfying $P < k \le i$, the maximum of $A[k..i]$ is strictly $A[i]$. For $k \le P$, the maximum value matches that of the subarray ending at $P$. This observation yields the recurrence: $$ DP_{max}[i] = DP_{max}[P] + A[i] \times (i - P) $$ If no such $P$ exists, $P$ defaults to $-1$, and the term $DP_{max}[P]$ vanishes. The index $P$ is retrieved in amortized constant time by maintaining a monotonically decreasing stack. The minimum accumulation $DP_{min}[i]$ follows an identical pattern using a monotonically increasing stack. Both passes execute in $O(N)$ time.

#include <iostream>
#include <vector>
#include <stack>

using ll = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    if (!(std::cin >> n)) return 0;

    std::vector<int> arr(n);
    for (int &val : arr) std::cin >> val;

    std::vector<ll> max_suffix_sum(n), min_suffix_sum(n);
    std::stack<int> dec_stk, inc_stk;

    for (int i = 0; i < n; ++i) {
        while (!dec_stk.empty() && arr[dec_stk.top()] <= arr[i]) {
            dec_stk.pop();
        }
        int prev_max_idx = dec_stk.empty() ? -1 : dec_stk.top();
        max_suffix_sum[i] = (prev_max_idx == -1 ? 0 : max_suffix_sum[prev_max_idx]) +
                            static_cast<ll>(arr[i]) * (i - prev_max_idx);
        dec_stk.push(i);

        while (!inc_stk.empty() && arr[inc_stk.top()] >= arr[i]) {
            inc_stk.pop();
        }
        int prev_min_idx = inc_stk.empty() ? -1 : inc_stk.top();
        min_suffix_sum[i] = (prev_min_idx == -1 ? 0 : min_suffix_sum[prev_min_idx]) +
                            static_cast<ll>(arr[i]) * (i - prev_min_idx);
        inc_stk.push(i);
    }

    ll total_diff = 0;
    for (int i = 0; i < n; ++i) {
        total_diff += max_suffix_sum[i] - min_suffix_sum[i];
    }

    std::cout << total_diff << '\n';
    return 0;
}

Strategy 2: Element Contribution Analysis

The original expression separates into independent maximum and minimum summations: $$ \sum_{L, R} \max(A[L..R]) - \sum_{L, R} \min(A[L..R]) $$ Focus on the maximum component. Determine how many contiguous subarrays designate $A[i]$ as their maximum element. Define $Left[i]$ as the closest index to the left where $A[Left[i]] > A[i]$, and $Right[i]$ as the closest index to the right where $A[Right[i]] \ge A[i]$. The asymmetric comparison operators prevent duplicate counting when equal values appear. Within the exclusive range $(Left[i], Right[i])$, $A[i]$ dominates. The number of valid subarrays is $(i - Left[i]) \times (Right[i] - i)$.

The total contribution of $A[i]$ to the maximum sum is $A[i] \times (i - Left[i]) \times (Right[i] - i)$. The minimum sum applies symmetric boundary conditions ($<$ on the left, $\le$ on the right). Precomputing all boundaries requires four linear scans with monotonic stacks, maintaining an overall $O(N)$ complexity.

#include <iostream>
#include <vector>
#include <stack>

using ll = long long;

std::vector<int> compute_left_limits(const std::vector<int>& data, bool tracking_max) {
    int n = data.size();
    std::vector<int> limits(n, -1);
    std::stack<int> stk;
    for (int i = 0; i < n; ++i) {
        while (!stk.empty() && (tracking_max ? data[stk.top()] <= data[i] : data[stk.top()] >= data[i])) {
            stk.pop();
        }
        limits[i] = stk.empty() ? -1 : stk.top();
        stk.push(i);
    }
    return limits;
}

std::vector<int> compute_right_limits(const std::vector<int>& data, bool tracking_max) {
    int n = data.size();
    std::vector<int> limits(n, n);
    std::stack<int> stk;
    for (int i = n - 1; i >= 0; --i) {
        while (!stk.empty() && (tracking_max ? data[stk.top()] < data[i] : data[stk.top()] > data[i])) {
            stk.pop();
        }
        limits[i] = stk.empty() ? n : stk.top();
        stk.push(i);
    }
    return limits;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    if (!(std::cin >> n)) return 0;

    std::vector<int> seq(n);
    for (int &x : seq) std::cin >> x;

    auto max_L = compute_left_limits(seq, true);
    auto max_R = compute_right_limits(seq, true);
    auto min_L = compute_left_limits(seq, false);
    auto min_R = compute_right_limits(seq, false);

    ll result = 0;
    for (int i = 0; i < n; ++i) {
        ll max_occurrences = static_cast<ll>(i - max_L[i]) * (max_R[i] - i);
        ll min_occurrences = static_cast<ll>(i - min_L[i]) * (min_R[i] - i);
        result += seq[i] * (max_occurrences - min_occurrences);
    }

    std::cout << result << '\n';
    return 0;
}