SyntaxPilot
Courses/Competitive Programming/Lesson 70
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 70 of 90

Monotonic stack and deque in contest problems

queued

These are the notes for Competitive Programming episode 70. A monotonic stack is a stack of indices whose values stay sorted; a monotonic deque is the same thing with an expiring front. Both turn many O(n²) contest problems into O(n), because every index is pushed once and popped at most once (amortised analysis). Cold Streaks (the sum of the minimum of every subarray) uses contribution counting with nearest-smaller indices, and a real tie-breaking bug that passes the sample but fails a stress test (8 instead of 6 on 2 2). Calm Window (the longest window with max − min ≤ d) uses two pointers with two monotonic deques, and a real infinite loop (TLE on an 8-number sample) when expired indices aren't dropped. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

Walk down a street of shops, each with a price, and at every shop ask: where is the nearest cheaper shop behind me? When a new, cheap shop opens, every shop behind it that is at least as expensive can never be anyone's answer again: for every later shop, the new one is both closer and cheaper. Throw those away. What's left is a short list whose prices fall as you look back, and its top is the answer. Each shop joins the list once and leaves once: linear time. That list is a monotonic stack.

Problem R1 · Cold Streaks

(Written for this course.)

  • n daily temperatures a1..an (n ≤ 10^6, 1 ≤ ai ≤ 10^6).
  • For every period l..r of consecutive days, take its coldest temperature. Print the sum over all periods.
  • The answer can reach about 5·10^17: use long long.
4
3 1 2 4

Periods from day 1: 3, 1, 1, 1; from day 2: 1, 1, 1; then 2, 2; then 4. Total 17.

Attempt 1: every period (TLE)

The brute force is kept as the checker for the stress test.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll brute(const vector<ll>& a) {                // every period l..r
    int n = a.size();
    ll total = 0;
    for (int l = 0; l < n; l++) {
        ll mn = a[l];
        for (int r = l; r < n; r++) {
            mn = min(mn, a[r]);                 // coldest day of l..r
            total += mn;
        }
    }
    return total;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto& x : a) cin >> x;
    cout << brute(a) << "\n";
}
17
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll brute(const vector<ll>& a) {                // every period l..r
    int n = a.size();
    ll total = 0;
    for (int l = 0; l < n; l++) {
        ll mn = a[l];
        for (int r = l; r < n; r++) {
            mn = min(mn, a[r]);                 // coldest day of l..r
            total += mn;
        }
    }
    return total;
}

int main() {
    int n = 1000000;                              // a million days
    mt19937 gen(70);
    vector<ll> a(n);
    for (auto& x : a) x = gen() % 1000000 + 1;
    cout << brute(a) << "\n";
}
Time Limit Exceeded

About n²/2 = 5·10^11 periods.

The key observation: count contributions

Turn the sum around: for every day i, count the periods in which a[i] is the minimum.

  • L[i] = the nearest colder day on the left, R[i] = the nearest colder day on the right.
  • The period may start at L+1..i and end at i..R−1: (i − L)·(R − i) periods.
  • answer = Σ a[i]·(i − L[i])·(R[i] − i). In the sample, the 1 on day 2 has no colder day anywhere: 2 starts × 3 ends = 6 periods, contributing 6.

The monotonic stack

  • Left to right: while the top is ≥ a[i], pop; L[i] = the top (or −1); push i.
  • Right to left: the same gives R[i] (or n).
  • The stack holds indices whose values increase from bottom to top. n pushes and at most n pops: O(n) even with a while inside the for.

Bug: strict on both sides (passes the sample!)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll fast(const vector<ll>& a) {
    int n = a.size();
    vector<int> L(n), R(n), st;
    for (int i = 0; i < n; i++) {                // previous strictly colder day
        while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
        L[i] = st.empty() ? -1 : st.back();
        st.push_back(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; i--) {           // next strictly colder day
        while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
        R[i] = st.empty() ? n : st.back();
        st.push_back(i);
    }
    ll total = 0;
    for (int i = 0; i < n; i++) total += a[i] * (i - L[i]) * (R[i] - i);
    return total;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto& x : a) cin >> x;
    cout << fast(a) << "\n";
}
17

The sample passes. A stress test with values 1..3 (lots of ties), which prints the failing input:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll brute(const vector<ll>& a) {                // every period l..r
    int n = a.size();
    ll total = 0;
    for (int l = 0; l < n; l++) {
        ll mn = a[l];
        for (int r = l; r < n; r++) {
            mn = min(mn, a[r]);                 // coldest day of l..r
            total += mn;
        }
    }
    return total;
}

ll fast(const vector<ll>& a) {
    int n = a.size();
    vector<int> L(n), R(n), st;
    for (int i = 0; i < n; i++) {                // previous strictly colder day
        while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
        L[i] = st.empty() ? -1 : st.back();
        st.push_back(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; i--) {           // next strictly colder day
        while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
        R[i] = st.empty() ? n : st.back();
        st.push_back(i);
    }
    ll total = 0;
    for (int i = 0; i < n; i++) total += a[i] * (i - L[i]) * (R[i] - i);
    return total;
}

int main() {
    mt19937 gen(7);
    for (int t = 1; t <= 500; t++) {
        int n = gen() % 5 + 1;
        vector<ll> a(n);
        for (auto& x : a) x = gen() % 3 + 1;   // tiny values: lots of ties
        if (brute(a) != fast(a)) {
            cout << "mismatch on test " << t << ": ";
            for (ll x : a) cout << x << " ";
            return 0;
        }
    }
    cout << "all 500 tests passed";
}
mismatch on test 3: 3 3 2

Shrink it to two equal days, 2 2:

8

The periods are 2, 2 and 2 2: 6. The period 2 2 has two coldest days, and both claimed it: counted twice.

The fix: break ties one way

Strictly colder on the left (pop while >=), colder or equal on the right (pop while >). Each day's periods now stop before the next equal day on its right, so a period with several equal minimums belongs to exactly one of them (the rightmost).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll fast(const vector<ll>& a) {
    int n = a.size();
    vector<int> L(n), R(n), st;
    for (int i = 0; i < n; i++) {                // previous strictly colder day
        while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
        L[i] = st.empty() ? -1 : st.back();
        st.push_back(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; i--) {           // next colder-or-equal day
        while (!st.empty() && a[st.back()] > a[i]) st.pop_back();
        R[i] = st.empty() ? n : st.back();
        st.push_back(i);
    }
    ll total = 0;
    for (int i = 0; i < n; i++) total += a[i] * (i - L[i]) * (R[i] - i);
    return total;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto& x : a) cin >> x;
    cout << fast(a) << "\n";
}
6
17
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll fast(const vector<ll>& a) {
    int n = a.size();
    vector<int> L(n), R(n), st;
    for (int i = 0; i < n; i++) {                // previous strictly colder day
        while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
        L[i] = st.empty() ? -1 : st.back();
        st.push_back(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; i--) {           // next colder-or-equal day
        while (!st.empty() && a[st.back()] > a[i]) st.pop_back();
        R[i] = st.empty() ? n : st.back();
        st.push_back(i);
    }
    ll total = 0;
    for (int i = 0; i < n; i++) total += a[i] * (i - L[i]) * (R[i] - i);
    return total;
}

int main() {
    int n = 1000000;                              // a million days
    mt19937 gen(70);
    vector<ll> a(n);
    for (auto& x : a) x = gen() % 1000000 + 1;
    cout << fast(a) << "\n";
}
13073683325672

A few hundredths of a second for a million days. The stress test now passes:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll brute(const vector<ll>& a) {                // every period l..r
    int n = a.size();
    ll total = 0;
    for (int l = 0; l < n; l++) {
        ll mn = a[l];
        for (int r = l; r < n; r++) {
            mn = min(mn, a[r]);                 // coldest day of l..r
            total += mn;
        }
    }
    return total;
}

ll fast(const vector<ll>& a) {
    int n = a.size();
    vector<int> L(n), R(n), st;
    for (int i = 0; i < n; i++) {                // previous strictly colder day
        while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
        L[i] = st.empty() ? -1 : st.back();
        st.push_back(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; i--) {           // next colder-or-equal day
        while (!st.empty() && a[st.back()] > a[i]) st.pop_back();
        R[i] = st.empty() ? n : st.back();
        st.push_back(i);
    }
    ll total = 0;
    for (int i = 0; i < n; i++) total += a[i] * (i - L[i]) * (R[i] - i);
    return total;
}

int main() {
    mt19937 gen(7);
    for (int t = 1; t <= 500; t++) {
        int n = gen() % 5 + 1;
        vector<ll> a(n);
        for (auto& x : a) x = gen() % 3 + 1;   // tiny values: lots of ties
        if (brute(a) != fast(a)) {
            cout << "mismatch on test " << t << ": ";
            for (ll x : a) cout << x << " ";
            return 0;
        }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Problem R2 · Calm Window

(Written for this course.)

  • The same kind of temperature list and a number d (n ≤ 10^6, 0 ≤ ai, d ≤ 10^9).
  • Print the length of the longest period l..r with max − min ≤ d.
8 2
5 6 4 7 6 6 5 9

With d = 2 the longest calm window is 7 6 6 5: 4.

Attempt 1: extend every start (TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int brute(const vector<ll>& a, ll d) {
    int n = a.size(), best = 0;
    for (int l = 0; l < n; l++) {
        ll mn = a[l], mx = a[l];
        for (int r = l; r < n; r++) {
            mn = min(mn, a[r]), mx = max(mx, a[r]);
            if (mx - mn > d) break;
            best = max(best, r - l + 1);
        }
    }
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll d;
    cin >> n >> d;
    vector<ll> a(n);
    for (auto& x : a) cin >> x;
    cout << brute(a, d) << "\n";
}
4

With d = 10^9 every window is calm, so every start runs to the end:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int brute(const vector<ll>& a, ll d) {
    int n = a.size(), best = 0;
    for (int l = 0; l < n; l++) {
        ll mn = a[l], mx = a[l];
        for (int r = l; r < n; r++) {
            mn = min(mn, a[r]), mx = max(mx, a[r]);
            if (mx - mn > d) break;
            best = max(best, r - l + 1);
        }
    }
    return best;
}

int main() {
    int n = 1000000;
    ll d = 1000000000;                            // every window is calm
    mt19937 gen(70);
    vector<ll> a(n);
    for (auto& x : a) x = gen() % 1000000001;
    cout << brute(a, d) << "\n";
}
Time Limit Exceeded

Two pointers + two monotonic deques

  • A window inside a calm window is calm, so two pointers work: move r right; while the window is too wide, move l right. Both pointers only move forward.
  • mx: indices with values falling from front to back; its front is the window maximum. Before pushing r, pop every back index whose value is ≤ a[r].
  • mn: indices with values rising; its front is the window minimum.
  • When l passes an index at a front, that day has left the window: pop it from the front.

Bug: never dropping expired indices (TLE on the sample)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int fast(const vector<ll>& a, ll d) {
    int n = a.size(), best = 0, l = 0;
    deque<int> mx, mn;                       // indices: values falling / rising
    for (int r = 0; r < n; r++) {
        while (!mx.empty() && a[mx.back()] <= a[r]) mx.pop_back();
        while (!mn.empty() && a[mn.back()] >= a[r]) mn.pop_back();
        mx.push_back(r), mn.push_back(r);
        while (a[mx.front()] - a[mn.front()] > d) {   // too hot: shrink
            l++;
        }
        best = max(best, r - l + 1);
    }
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll d;
    cin >> n >> d;
    vector<ll> a(n);
    for (auto& x : a) cin >> x;
    cout << fast(a, d) << "\n";
}
Time Limit Exceeded

On an 8-number input a TLE can't be slowness: it's an infinite loop. The fronts never change, so a[mx.front()] - a[mn.front()] > d stays true forever and l runs away.

The fix

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int fast(const vector<ll>& a, ll d) {
    int n = a.size(), best = 0, l = 0;
    deque<int> mx, mn;                       // indices: values falling / rising
    for (int r = 0; r < n; r++) {
        while (!mx.empty() && a[mx.back()] <= a[r]) mx.pop_back();
        while (!mn.empty() && a[mn.back()] >= a[r]) mn.pop_back();
        mx.push_back(r), mn.push_back(r);
        while (a[mx.front()] - a[mn.front()] > d) {   // too hot: shrink
            l++;
            if (mx.front() < l) mx.pop_front();   // drop days that left
            if (mn.front() < l) mn.pop_front();
        }
        best = max(best, r - l + 1);
    }
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll d;
    cin >> n >> d;
    vector<ll> a(n);
    for (auto& x : a) cin >> x;
    cout << fast(a, d) << "\n";
}

Sample, one day with d = 0, five equal days with d = 0:

4
1
5

The test that killed the brute force:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int fast(const vector<ll>& a, ll d) {
    int n = a.size(), best = 0, l = 0;
    deque<int> mx, mn;                       // indices: values falling / rising
    for (int r = 0; r < n; r++) {
        while (!mx.empty() && a[mx.back()] <= a[r]) mx.pop_back();
        while (!mn.empty() && a[mn.back()] >= a[r]) mn.pop_back();
        mx.push_back(r), mn.push_back(r);
        while (a[mx.front()] - a[mn.front()] > d) {   // too hot: shrink
            l++;
            if (mx.front() < l) mx.pop_front();   // drop days that left
            if (mn.front() < l) mn.pop_front();
        }
        best = max(best, r - l + 1);
    }
    return best;
}

int main() {
    int n = 1000000;
    ll d = 1000000000;                            // every window is calm
    mt19937 gen(70);
    vector<ll> a(n);
    for (auto& x : a) x = gen() % 1000000001;
    cout << fast(a, d) << "\n";
}
1000000
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int brute(const vector<ll>& a, ll d) {
    int n = a.size(), best = 0;
    for (int l = 0; l < n; l++) {
        ll mn = a[l], mx = a[l];
        for (int r = l; r < n; r++) {
            mn = min(mn, a[r]), mx = max(mx, a[r]);
            if (mx - mn > d) break;
            best = max(best, r - l + 1);
        }
    }
    return best;
}

int fast(const vector<ll>& a, ll d) {
    int n = a.size(), best = 0, l = 0;
    deque<int> mx, mn;                       // indices: values falling / rising
    for (int r = 0; r < n; r++) {
        while (!mx.empty() && a[mx.back()] <= a[r]) mx.pop_back();
        while (!mn.empty() && a[mn.back()] >= a[r]) mn.pop_back();
        mx.push_back(r), mn.push_back(r);
        while (a[mx.front()] - a[mn.front()] > d) {   // too hot: shrink
            l++;
            if (mx.front() < l) mx.pop_front();   // drop days that left
            if (mn.front() < l) mn.pop_front();
        }
        best = max(best, r - l + 1);
    }
    return best;
}

int main() {
    mt19937 gen(7);
    for (int t = 1; t <= 500; t++) {
        int n = gen() % 10 + 1;
        ll d = gen() % 4;
        vector<ll> a(n);
        for (auto& x : a) x = gen() % 6;
        if (brute(a, d) != fast(a, d)) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Complexity vs the constraints

Method Time Verdict (n = 10^6)
R1: every period O(n²) ≈ 5·10^11 TLE
R1: contributions + monotonic stack O(n) accepted (~0.04 s)
R2: extend every start O(n²) TLE
R2: two pointers + two deques O(n) accepted (~0.03 s)

Memory: a few arrays of n. Each index is pushed once and popped at most once from each stack/deque, so the inner while loops run at most n times in total (amortised O(1) per step).

Common mistakes (and the real outputs)

Mistake What you see Why Fix
strict comparison on both sides 8 instead of 6 on 2 2 ties counted twice >= on one side, > on the other
never dropping expired fronts Time Limit Exceeded on an 8-number sample the shrink loop never ends pop the front when its index < l
storing values instead of indices Wrong Answer can't tell when an element left the window store indices
int products Wrong Answer (overflow) the answer reaches ~10^17 long long
popping > instead of >= on the left as well Wrong Answer with ties ties end up claimed by nobody or twice write the tie rule down first
front() on an empty deque Runtime Error no element push r before reading the fronts

Mini project

Write a generic MonotonicQueue<T, Compare> with push(index, value), expire(l) and best(), and use it to print the maximum and the minimum of every window of size k. Stress test it against a brute force with many equal values.

Practice

These are the homework problems from the episode.

1. Sum of (max − min) over all subarrays. It equals (sum of maxima) − (sum of minima). The sum of maxima is the sum of minima of −a, negated.

2. Largest rectangle in a histogram. For every bar, the widest span where it is the lowest is between its nearest lower bars on both sides: one monotonic stack pass with a sentinel 0 at the end.

Solutions for 1 and 2 (checked against brute force on 100 random tests)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// sum over all subarrays of (max − min) = (sum of maxima) − (sum of minima)
ll contribution(vector<ll> a) {                    // sum of minima
    int n = a.size();
    vector<int> L(n), R(n), st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
        L[i] = st.empty() ? -1 : st.back();
        st.push_back(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && a[st.back()] > a[i]) st.pop_back();
        R[i] = st.empty() ? n : st.back();
        st.push_back(i);
    }
    ll total = 0;
    for (int i = 0; i < n; i++) total += a[i] * (i - L[i]) * (R[i] - i);
    return total;
}

int main() {
    int n;
    cin >> n;
    vector<ll> a(n), neg(n);
    for (int i = 0; i < n; i++) cin >> a[i], neg[i] = -a[i];
    ll sumMin = contribution(a), sumMax = -contribution(neg);   // max(a) = −min(−a)
    cout << sumMax - sumMin << "\n";
}
3
1 3 2
5
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {                                        // largest rectangle in a histogram
    int n;
    cin >> n;
    vector<ll> h(n);
    for (auto& x : h) cin >> x;
    vector<int> st;                                 // indices, heights rising
    ll best = 0;
    for (int i = 0; i <= n; i++) {
        ll cur = i < n ? h[i] : 0;                  // a 0 at the end empties the stack
        while (!st.empty() && h[st.back()] >= cur) {
            ll height = h[st.back()];
            st.pop_back();
            int left = st.empty() ? -1 : st.back(); // the bar spans left+1 .. i−1
            best = max(best, height * (i - left - 1));
        }
        st.push_back(i);
    }
    cout << best << "\n";
}
6
2 1 5 6 2 3
10

3. Count every window with max − min ≤ d. In the R2 loop, after shrinking, every window ending at r and starting at l..r is calm: add r − l + 1 to a long long total.

Hint

Replace best = max(best, r - l + 1) with total += r - l + 1. The answer for n = 10^6 can reach about 5·10^11.

4. Sliding-window maximum of size k. One falling deque of indices: push r, drop the front if it's ≤ r − k, and print a[front] once r ≥ k − 1.

Hint

It's the mx deque of R2 with a fixed window: if (mx.front() <= r - k) mx.pop_front();

Quick quiz

a = 2 5 3 4 1
// for each i: the nearest value to the left
// that is strictly smaller (- if none)

A) - 2 2 3 - · B) - 2 5 3 - · C) - 2 2 3 1 · D) 2 5 3 4 -

Answer

A. 5 sees 2; 3 pops 5 and sees 2; 4 sees 3; 1 pops everything, so none.

Interview questions

  1. What is a monotonic stack? A stack of indices whose values stay increasing (or decreasing); each new element pops the ones it dominates.
  2. Why is it O(n) with a while loop inside? Every index is pushed once and popped at most once, so all pops together are at most n.
  3. What does contribution counting mean? Instead of computing something for every subarray, count how many subarrays each element affects and add element × count.
  4. How do you handle equal values in the sum of minimums? Make the comparison strict on one side and non-strict on the other, so every subarray has exactly one owner.
  5. Monotonic stack vs deque? A deque also drops elements from its front when they leave a sliding window.
  6. Why store indices instead of values? To know when an element has left the window, and to keep equal values apart.
  7. How do you spot an infinite loop in a contest? A TLE on a tiny input (the sample) is almost never slowness.

Glossary

Term Meaning Example
Monotonic stack A stack whose values stay sorted from bottom to top nearest colder day
Monotonic deque A monotonic stack that can also drop its oldest end window max and min
Deque Double-ended queue: push and pop at both ends deque<int>
Nearest smaller element The closest index to one side with a smaller value L[i], R[i]
Contribution counting Sum element × (number of subarrays it affects) a[i]·(i − L)·(R − i)
Subarray / period A contiguous block a[l..r] days 2..4
Tie-breaking A rule that gives equal values exactly one owner >= left, > right
Amortised analysis Total cost over all steps, not per step n pushes, ≤ n pops
Two pointers Two indices that only move forward over the array l and r
Sliding window The current range l..r of two pointers the calm window
Expired index An index that has left the window (< l) pop the front
Dominated element One that can never be the answer again a pricier shop behind a cheaper one
Infinite loop A loop whose condition never becomes false TLE on the sample
Overflow A value too big for its type use long long
Stress test Fast vs brute force on many small random inputs mismatch on test 3: 3 3 2
String hashing Fingerprints for substrings next episode

Summary

  • Sum over all subarrays? Count each element's contribution; nearest smaller indices come from a monotonic stack in O(n).
  • With equal values, compare strictly on one side and non-strictly on the other, or ties are counted twice. The sample may not show it: stress test.
  • Moving windows: two pointers + two monotonic deques of indices, dropping expired fronts. O(n).
  • A TLE on a tiny input means an infinite loop.

Solutions in C++, Java and Python

Problem R1 · Cold Streaks

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll fast(const vector<ll>& a) {
    int n = a.size();
    vector<int> L(n), R(n), st;
    for (int i = 0; i < n; i++) {                // previous strictly colder day
        while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
        L[i] = st.empty() ? -1 : st.back();
        st.push_back(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; i--) {           // next colder-or-equal day
        while (!st.empty() && a[st.back()] > a[i]) st.pop_back();
        R[i] = st.empty() ? n : st.back();
        st.push_back(i);
    }
    ll total = 0;
    for (int i = 0; i < n; i++) total += a[i] * (i - L[i]) * (R[i] - i);
    return total;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto& x : a) cin >> x;
    cout << fast(a) << "\n";
}

Java (checked on the samples and 10 random tests against the C++ brute force)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
        int n = nextInt(in);
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = nextInt(in);
        int[] L = new int[n], R = new int[n], st = new int[n];
        int top = 0;
        for (int i = 0; i < n; i++) {                       // previous strictly colder day
            while (top > 0 && a[st[top - 1]] >= a[i]) top--;
            L[i] = top == 0 ? -1 : st[top - 1];
            st[top++] = i;
        }
        top = 0;
        for (int i = n - 1; i >= 0; i--) {                  // next colder-or-equal day
            while (top > 0 && a[st[top - 1]] > a[i]) top--;
            R[i] = top == 0 ? n : st[top - 1];
            st[top++] = i;
        }
        long total = 0;
        for (int i = 0; i < n; i++) total += a[i] * (i - L[i]) * (R[i] - i);
        System.out.println(total);
    }

    static int nextInt(DataInputStream in) throws IOException {
        int r = 0, b = in.read();
        while (b < '0') b = in.read();
        while (b >= '0') { r = r * 10 + b - '0'; b = in.read(); }
        return r;
    }
}

Python (Python ints never overflow)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); a = list(map(int, data[1:1 + n]))
    L, R, st = [-1] * n, [n] * n, []
    for i in range(n):                          # previous strictly colder day
        while st and a[st[-1]] >= a[i]: st.pop()
        L[i] = st[-1] if st else -1
        st.append(i)
    st = []
    for i in range(n - 1, -1, -1):              # next colder-or-equal day
        while st and a[st[-1]] > a[i]: st.pop()
        R[i] = st[-1] if st else n
        st.append(i)
    print(sum(a[i] * (i - L[i]) * (R[i] - i) for i in range(n)))

main()

Problem R2 · Calm Window

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int fast(const vector<ll>& a, ll d) {
    int n = a.size(), best = 0, l = 0;
    deque<int> mx, mn;                       // indices: values falling / rising
    for (int r = 0; r < n; r++) {
        while (!mx.empty() && a[mx.back()] <= a[r]) mx.pop_back();
        while (!mn.empty() && a[mn.back()] >= a[r]) mn.pop_back();
        mx.push_back(r), mn.push_back(r);
        while (a[mx.front()] - a[mn.front()] > d) {   // too hot: shrink
            l++;
            if (mx.front() < l) mx.pop_front();   // drop days that left
            if (mn.front() < l) mn.pop_front();
        }
        best = max(best, r - l + 1);
    }
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll d;
    cin >> n >> d;
    vector<ll> a(n);
    for (auto& x : a) cin >> x;
    cout << fast(a, d) << "\n";
}

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
        int n = (int) nextLong(in);
        long d = nextLong(in);
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = nextLong(in);
        int[] mx = new int[n], mn = new int[n];          // deques as arrays: [head, tail)
        int mxH = 0, mxT = 0, mnH = 0, mnT = 0, l = 0, best = 0;
        for (int r = 0; r < n; r++) {
            while (mxT > mxH && a[mx[mxT - 1]] <= a[r]) mxT--;
            while (mnT > mnH && a[mn[mnT - 1]] >= a[r]) mnT--;
            mx[mxT++] = r; mn[mnT++] = r;
            while (a[mx[mxH]] - a[mn[mnH]] > d) {       // too hot: shrink
                l++;
                if (mx[mxH] < l) mxH++;                 // drop days that left
                if (mn[mnH] < l) mnH++;
            }
            best = Math.max(best, r - l + 1);
        }
        System.out.println(best);
    }

    static long nextLong(DataInputStream in) throws IOException {
        long r = 0; int b = in.read();
        while (b < '0') b = in.read();
        while (b >= '0') { r = r * 10 + b - '0'; b = in.read(); }
        return r;
    }
}

Python

import sys
from collections import deque

def main():
    data = sys.stdin.buffer.read().split()
    n, d = int(data[0]), int(data[1]); a = list(map(int, data[2:2 + n]))
    mx, mn = deque(), deque()                   # indices: values falling / rising
    l = best = 0
    for r in range(n):
        while mx and a[mx[-1]] <= a[r]: mx.pop()
        while mn and a[mn[-1]] >= a[r]: mn.pop()
        mx.append(r); mn.append(r)
        while a[mx[0]] - a[mn[0]] > d:          # too hot: shrink
            l += 1
            if mx[0] < l: mx.popleft()          # drop days that left
            if mn[0] < l: mn.popleft()
        best = max(best, r - l + 1)
    print(best)

main()