单调栈与单调队列

// 柱状图里最大的矩形 —— 标准答案：枚举所有区间 O(n²)
//
// 这份代码为什么存在：它是对拍的**标准答案**，所以第一要务不是快，是**思路和正解完全不同**。
//
// 正解（fast.cpp）想的是「对每一根柱子，它能往左右扩到哪里」；
// 这一份想的是「**每一段连续的柱子**都试一遍」：
//   一段 [l, r] 能勾出的矩形，高是这一段里**最矮的那根**，宽是 r-l+1。
//   把所有 O(n²) 段都试一遍，取最大。
//
// ★ 注意 `mn` 是**边扫边更新**的（min 是可以增量维护的），所以是 O(n²) 而不是 O(n³)。
//
// ⚠ 更要紧的是：这两层循环里**一次 break 都没有**，n² 就老老实实是 n²。
//   （第 25、30、31 章那条「要证明暴力慢，先确认它真的走到底了」——
//    这一章还有一份 expand.cpp 专门演示反面：那份带 break 的暴力在随机数据上快得像 O(n)。）
//
// 输入：第一行 n；第二行 n 个整数 h[1..n]（0 ≤ h[i] ≤ 10⁹）
// 输出：一个整数 —— 最大矩形面积
//
// ⚠ 面积最大可到 n × max(h) = 2×10⁵ × 10⁹，**必须 long long**（int 会溢出）。
//   而这件事**对拍在小数据上永远查不出来** —— 见 wrongInt.cpp。

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

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

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> h(n + 1);
    for (int i = 1; i <= n; i++) cin >> h[i];

    long long ans = 0;
    for (int l = 1; l <= n; l++) {
        long long mn = LLONG_MAX;
        for (int r = l; r <= n; r++) {
            mn = min(mn, h[r]);                 // 这一段里最矮的那根
            ans = max(ans, mn * (r - l + 1));   // 高 × 宽
        }
    }
    cout << ans << "\n";
    return 0;
}

// 柱状图 —— 另一份「看起来更聪明」的 O(n²) 暴力：以每根柱子为高，往左右扩
//
// 这份代码为什么存在：★ 它是本教材第四次演示「**暴力会假装自己不慢**」，
// 而且这一次那个旋钮既不是规模、也不是密度，是**数据的形状**。
//
// 它的思路和正解（fast.cpp）其实一模一样 ——「对每根柱子求左右第一个更矮的」——
// 只是老老实实地一根一根往外挪：
//
//     while (l >= 1  && h[l] >= h[i]) l--;      // ← ★ 这两句里各有一个 break 的意思：
//     while (r <= n  && h[r] >= h[i]) r++;      //   「一碰到更矮的就停」
//
// 最坏情况确实是 O(n²)（比如 h 单调不降时，每根都要一路扩到头）。
// 可**随机数据上它快得像 O(n)**：随便扔一根柱子下去，左右两边往往走一两格就碰到更矮的了。
//
// 本机实测（./genBig n 0 = 随机，./genBig n 1 = 单调不降），见正文第 13 步那张表：
//   随机   n = 200000：0.02 秒（两个 while 一共挪了 4097 万步）
//   单调不降 n = 200000：★ 7.10 秒（挪了 200.2 亿步 —— 正好是 n²/2）
//   ★ 同一份代码、同样的 n，差 489 倍。
//
// ⚠ 所以拿它做「暴力有多慢」的对比表时，**数据形状选错，整张表就是废的**：
//   第 25 章是容量给小了（免费剪枝），第 30 章是图太稀疏，第 31 章是「找到第一个就 break」，
//   这一章是**数据不够单调**。四次的共同点只有一句：
//   ★ **量之前，先确认暴力真的把该做的活都做了。**
//
// 用法：
//   ./expand            读入柱状图，输出最大面积（和 brute.cpp / fast.cpp 必须一致）
//   ./expand count      多输出一个数：★ 两个 while 一共挪了多少步（正文那张表就是它）

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

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    bool showCount = (argc > 1 && string(argv[1]) == "count");

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> h(n + 2);
    for (int i = 1; i <= n; i++) cin >> h[i];

    long long ans = 0, steps = 0;
    for (int i = 1; i <= n; i++) {
        int l = i, r = i;
        while (l - 1 >= 1 && h[l - 1] >= h[i]) { l--; steps++; }   // ★ 一碰到更矮的就停
        while (r + 1 <= n && h[r + 1] >= h[i]) { r++; steps++; }
        steps += 2;                                                // 那两次「停下来」的判断也算
        ans = max(ans, h[i] * (r - l + 1));
    }

    cout << ans;
    if (showCount) cout << " " << steps;
    cout << "\n";
    return 0;
}

// 柱状图里最大的矩形 —— 正解：单调栈 O(n)
//
// 这份代码为什么存在：它是本章的主角。
//
// ★ 换一个问法就全通了：**以第 t 根柱子的高度为高**的最大矩形，宽能有多少？
//   往左能扩到「左边第一根**比它矮**的柱子」的右边，往右扩到「右边第一根比它矮的」的左边。
//   于是问题变成：**对每一根柱子，求出它左右两侧第一个更矮的柱子在哪。**
//   （★ 请注意：问的是**位置**，不是值 —— 所以栈里存的必须是**下标**。）
//
// 单调栈就是干这个的：栈里的下标，对应的高度**从栈底到栈顶严格递增**。
//   新来一根 cur，把栈顶所有「不比 cur 矮」的都弹掉 ——
//   对每个被弹出的 t，此刻的两件事同时揭晓：
//     · 右边第一个比它矮的，就是**当前这个 i**；
//     · 左边第一个比它矮的，就是**它被弹掉之后的新栈顶**（因为栈里是递增的）。
//   所以宽 = i − 新栈顶 − 1（★ 那个 −1 是「不含两端那两根更矮的」，wrongWidth.cpp 就错在这里）。
//
// ★★ 关键一步是**均摊分析**：这里明明有两层循环（for 里套 while），但它是 O(n) ——
//   因为每根柱子**一辈子只入栈一次、只出栈一次**，那句 while 转的总次数不会超过 n。
//   这和第 7 章双指针「两个指针都只往前走，所以是 O(n)」是同一件事。
//   count.cpp 把这两个次数数出来给你看。
//
// ⚠ 末尾那根 −1 的哨兵：扫完之后栈里通常还剩一串（越往栈顶越高），
//   它们的右边界还没揭晓。放一根「比所有柱子都矮」的哨兵，就能把它们全逼出来，
//   主循环一个字都不用改。忘了这件事就是 wrongTail.cpp。
//   ⚠ 为什么写 −1 而不是 0：题目允许 h = 0，写 −1 才**严格**比所有柱子矮，一句话就说得清。
//   （这道题写 0 其实也对 —— 高 0 的柱子面积也是 0，漏算了也不影响最大值 ——
//    但那要多想一步。★ 哨兵的意义就是「不用多想一步」，别给自己留这种账。）
//
// 输入输出同 brute.cpp。

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

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

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> h(n + 2);
    for (int i = 1; i <= n; i++) cin >> h[i];
    h[n + 1] = -1;                       // 哨兵：比任何柱子都矮，把栈里剩下的全逼出来

    long long ans = 0;
    vector<int> st;                      // ★ 存的是**下标**，对应高度严格递增
    st.reserve(n + 1);

    for (int i = 1; i <= n + 1; i++) {
        while (!st.empty() && h[st.back()] >= h[i]) {
            int t = st.back();
            st.pop_back();
            long long left = st.empty() ? 0 : st.back();   // 左边第一个比 h[t] 矮的下标（没有就当 0）
            long long w = i - left - 1;
            ans = max(ans, h[t] * w);
        }
        st.push_back(i);
    }

    cout << ans << "\n";
    return 0;
}

// 柱状图 —— 把三种写法的**工作量**数出来（★ 均摊分析的证据）
//
// 这份代码为什么存在：「单调栈是 O(n)」这句话，光看代码是不服气的 ——
// 明明 for 里面套了个 while。所以这里不讲道理，直接数：
//
//   · 入栈次数、出栈次数 —— ★ **入栈 n+1 次（含哨兵）、出栈 n 次**（哨兵只进不出，没人来弹它），
//     不管数据长什么样，一次不多一次不少。这就是均摊分析那句「每个元素进出各一次」的**实物**。
//   · while 的判断次数 —— 它比出栈次数只多一点点（每次 for 循环最多多判一次「不弹了」）。
//   · 枚举区间的暴力（brute.cpp）：n(n+1)/2 次，一次都少不了。
//   · 往外扩的暴力（expand.cpp）：★ 这个数**随数据形状剧烈变化** ——
//     随机数据上它和 n 一个量级，单调不降时才涨到 n²/2。
//
// ⚠ 第 29、32、34 章那条「**量之前先确认「你量的就是它」**」在这里的落法：
//   这份程序只做「数数」这一件事，不做任何输出格式化、也不重复读入 ——
//   三种写法读的是同一份输入、数的是同一件事（「碰了多少次数据」）。
//
// 输入：同 brute.cpp
// 输出：一张表（正文第 6 步引用了其中三个数）

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

/** 含中文的列不能用 setw（它数字节，一个汉字 3 字节只占 2 格宽）—— 第 26 章那个 padDisp */
static string padDisp(const string& s, int width) {
    int disp = 0;
    for (size_t i = 0; i < s.size();) {
        unsigned char c = s[i];
        if (c < 0x80) { disp += 1; i += 1; }
        else if ((c >> 5) == 6) { disp += 1; i += 2; }
        else if ((c >> 4) == 14) { disp += 2; i += 3; }
        else { disp += 2; i += 4; }
    }
    return s + string(max(0, width - disp), ' ');
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<long long> h(n + 2);
    for (int i = 1; i <= n; i++) cin >> h[i];
    h[n + 1] = -1;

    /* ① 单调栈：入栈 / 出栈 / while 判断各多少次 */
    long long pushes = 0, pops = 0, tests = 0, ans = 0;
    {
        vector<int> st;
        for (int i = 1; i <= n + 1; i++) {
            while (true) {
                tests++;                              // 每转一圈都要判一次（包括最后那次「不弹了」）
                if (st.empty() || h[st.back()] < h[i]) break;
                int t = st.back();
                st.pop_back();
                pops++;
                long long left = st.empty() ? 0 : st.back();
                ans = max(ans, h[t] * (i - left - 1));
            }
            st.push_back(i);
            pushes++;
        }
    }

    /* ② 枚举区间的暴力：n(n+1)/2 次，没有任何提前退出 */
    long long bruteSteps = (long long)n * (n + 1) / 2;

    /* ③ 往外扩的暴力：★ 这个数完全取决于数据长什么样 */
    long long expandSteps = 0;
    for (int i = 1; i <= n; i++) {
        int l = i, r = i;
        while (l - 1 >= 1 && h[l - 1] >= h[i]) { l--; expandSteps++; }
        while (r + 1 <= n && h[r + 1] >= h[i]) { r++; expandSteps++; }
        expandSteps += 2;
    }

    printf("n = %d，答案 = %lld\n\n", n, ans);
    printf("%s%s\n", padDisp("写法", 30).c_str(), padDisp("碰数据的次数", 16).c_str());
    printf("%s\n", string(46, '-').c_str());
    printf("%s%lld\n", padDisp("★ 单调栈：入栈", 30).c_str(), pushes);
    printf("%s%lld\n", padDisp("★ 单调栈：出栈", 30).c_str(), pops);
    printf("%s%lld\n", padDisp("   单调栈：while 判断", 30).c_str(), tests);
    printf("%s%lld\n", padDisp("   枚举所有区间（brute）", 30).c_str(), bruteSteps);
    printf("%s%lld\n", padDisp("   往左右扩（expand）", 30).c_str(), expandSteps);
    printf("\n★ 入栈 %lld 次 = n+1（含哨兵）、出栈 %lld 次 = n —— 每根柱子进出各一次，"
           "和数据长什么样毫无关系。\n", pushes, pops);
    printf("  这就是「两层循环却是 O(n)」的全部理由：那句 while 转的总次数被出栈次数管死了。\n");
    return 0;
}

// 柱状图 —— 把单调栈**每一步**的栈内容打出来（动画就是照着这张表画的）
//
// 这份代码为什么存在：check:viz 拿它和网页动画**逐行**对（第 23 章 trace.cpp 的同款）。
// 只比最终答案是不够的 —— 那样「答案蒙对、过程画错」根本发现不了。
//
// 每一步打三样东西：
//   · 这一步弹出了几根（★ 这个数就是均摊分析的证据：它加起来正好是 n+1）
//   · 弹完之后栈里剩哪些**下标**（★ 对应的高度必须严格递增，动画那边也逐帧验这一条）
//   · 当前的答案
//
// ⚠ 这份程序 cout 和 printf 混用，所以**绝对不能关 ios::sync_with_stdio**
//   （第 26、28 章各踩过一次：两边各自缓冲，表格会跑到结语后面去）。
//
// 输入：同 brute.cpp
// 输出：一行一步，末尾一行汇总

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

/** 含中文的列不能用 %-Ns（它数字节，一个汉字 3 字节却只占 2 格宽）—— 第 26 章那个 padDisp */
static string padDisp(const string& s, int width) {
    int disp = 0;
    for (size_t i = 0; i < s.size();) {
        unsigned char c = s[i];
        if (c < 0x80) { disp += 1; i += 1; }
        else if ((c >> 5) == 6) { disp += 1; i += 2; }
        else if ((c >> 4) == 14) { disp += 2; i += 3; }
        else { disp += 2; i += 4; }
    }
    return s + string(max(0, width - disp), ' ');
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<long long> h(n + 2);
    for (int i = 1; i <= n; i++) cin >> h[i];
    h[n + 1] = -1;                              // 哨兵

    long long ans = 0, pushes = 0, pops = 0;
    vector<int> st;

    printf("%s%s%s%s%s\n", padDisp("步", 6).c_str(), padDisp("新来", 8).c_str(),
           padDisp("弹出", 10).c_str(), padDisp("栈内下标（高度递增）", 26).c_str(), "ans");
    printf("%s\n", string(64, '-').c_str());

    for (int i = 1; i <= n + 1; i++) {
        int popped = 0;
        while (!st.empty() && h[st.back()] >= h[i]) {
            int t = st.back();
            st.pop_back();
            popped++; pops++;
            long long left = st.empty() ? 0 : st.back();
            ans = max(ans, h[t] * (i - left - 1));
        }
        st.push_back(i);
        pushes++;

        string in = (i <= n) ? ("h=" + to_string(h[i])) : "哨兵";
        string body;
        for (int x : st) { if (!body.empty()) body += " "; body += to_string(x); }
        if (body.empty()) body = "空";
        printf("%s%s%s%s%lld\n",
               padDisp("步 " + to_string(i), 6).c_str(), padDisp(in, 8).c_str(),
               padDisp("弹出 " + to_string(popped) + " 根", 10).c_str(),
               padDisp("栈 [" + body + "]", 26).c_str(), ans);
    }

    printf("%s\n", string(64, '-').c_str());
    printf("★ 一共入栈 %lld 次、出栈 %lld 次（n = %d）—— 每根柱子进出各一次，"
           "哨兵只进不出（没人来弹它）。\n", pushes, pops, n);
    cout << "★ 这就是「for 里套 while 却是 O(n)」的全部理由：那句 while 转多少圈，"
            "被出栈次数管死了。\n";
    return 0;
}

// 滑动窗口最值 —— 标准答案：每个窗口老老实实扫一遍 O(nk)
//
// 这份代码为什么存在：它是对拍的**标准答案**，也是「题目到底在问什么」的定义本身。
//
// 窗口从左往右滑，每滑一格就把窗口里的 k 个数**从头扫一遍**，取最小、取最大。
// 一共 n−k+1 个窗口，每个窗口 k 个数 —— O(nk)。
//
// ⚠ 它和 fast 那份的关系，和柱状图那道题正好是一对：
//   那边的暴力（expand.cpp）带 break，会假装自己不慢；
//   这一份**一次 break 都没有**，k 有多大就扫多少下，n 和 k 都够大时它是真的慢。
//   （所以第 13 步那张耗时表的旋钮是 **k**，不是 n —— 这也是「要随机的是算法依赖的那个量」。）
//
// 输入：第一行 n 和 k（1 ≤ k ≤ n）；第二行 n 个整数 a[1..n]（可能是负数）
// 输出：第一行 n−k+1 个数 —— 每个窗口的**最小值**
//       第二行 n−k+1 个数 —— 每个窗口的**最大值**

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

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

    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int wantMin = 1; wantMin >= 0; wantMin--) {
        for (int i = k; i <= n; i++) {                 // 窗口是 [i-k+1, i]
            long long best = a[i - k + 1];
            for (int j = i - k + 2; j <= i; j++)
                best = wantMin ? min(best, a[j]) : max(best, a[j]);
            cout << best << " \n"[i == n];
        }
    }
    return 0;
}

// 滑动窗口最值 —— 正解：单调队列 O(n)
//
// 这份代码为什么存在：它是本章后半章的主角，也是**均摊分析的第二次登场**。
//
// ★ 关键一步和单调栈是同一句话，只是多了一头：
//   队列里存**下标**，对应的值单调（求最小值时递增）。
//   · **队尾**：新来一个 a[i]，把队尾所有「不比它小」的都弹掉 ——
//     理由是那些家伙**又老又大**，只要 a[i] 还在窗口里，它们永远轮不到当最小值。
//   · **队头**：如果队头那个下标已经滑出窗口（≤ i−k），弹掉。
//     ★ **这就是为什么队列里必须存下标**：光存值，你根本不知道它是什么时候进来的
//     （winWrongVal.cpp 就死在这里）。
//   于是队头永远是当前窗口的最小值，O(1) 取到。
//
// ★★ 还是均摊：每个下标**只入队一次、只出队一次**（要么被队尾挤掉、要么从队头滑走），
//   所以两个 while 加起来转不过 2n 圈。和单调栈、和第 7 章双指针，是同一件事的三张脸。
//
// ⚠ 单调栈和单调队列的区别只有一句：**单调栈只从一头进出，单调队列两头都要动** ——
//   多出来的那一头，管的正是「窗口有多宽」这件事。
//
// 输入输出同 winBrute.cpp。

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

/** wantMin = true 求每个窗口的最小值，false 求最大值 —— 两者只差一个不等号方向 */
static void solve(const vector<long long>& a, int n, int k, bool wantMin) {
    deque<int> q;                                     // ★ 存下标，不存值
    for (int i = 1; i <= n; i++) {
        // ① 队尾：把「又老又不如新来的」全弹掉
        while (!q.empty() && (wantMin ? a[q.back()] >= a[i] : a[q.back()] <= a[i]))
            q.pop_back();
        q.push_back(i);
        // ② 队头：滑出窗口的弹掉（一次最多滑出一个，所以 if 就够）
        if (q.front() <= i - k) q.pop_front();
        // ③ 从第 k 个数开始，每一格都有一个完整的窗口
        if (i >= k) cout << a[q.front()] << " \n"[i == n];
    }
}

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

    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    solve(a, n, k, true);
    solve(a, n, k, false);
    return 0;
}

// 滑动窗口 —— 把工作量数出来（★ 均摊分析的第二份证据），外加一个「只读入」的开关
//
// 这份代码为什么存在，有两个理由：
//
// ① ★ **入队次数和 k 一点关系都没有。** 暴力是 O(nk)，k 从 10 拧到 100000 慢了两百多倍；
//    而单调队列这边，不管 k 是多少，**入队次数恒等于 n**，队尾 + 队头的出队次数加起来也不超过 n。
//    这就是「两个 while 却是 O(n)」的实物证据。
//
// ② ⚠ **量之前先确认「你量的就是它」**（第 29、32、34 章那条，这是第四次）。
//    n = 200000 时正解跑完只要 0.03 秒 —— 可这 0.03 秒里**几乎全是读入**。
//    `./winCount io` 只读入、什么都不算，把那一截量出来减掉，才知道算法本身花了多少。
//
// 用法：
//   ./winCount        读入 + 数一遍工作量，打印一张表
//   ./winCount io     ★ 只读入，立刻退出（用来量「读入本身要多久」）
//
// 输入：同 winBrute.cpp

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

static string padDisp(const string& s, int width) {
    int disp = 0;
    for (size_t i = 0; i < s.size();) {
        unsigned char c = s[i];
        if (c < 0x80) { disp += 1; i += 1; }
        else if ((c >> 5) == 6) { disp += 1; i += 2; }
        else if ((c >> 4) == 14) { disp += 2; i += 3; }
        else { disp += 2; i += 4; }
    }
    return s + string(max(0, width - disp), ' ');
}

int main(int argc, char** argv) {
    bool ioOnly = (argc > 1 && string(argv[1]) == "io");

    // ⚠ 读入方式必须和 winFast.cpp / winBrute.cpp **一模一样**（同样是 cin + 关掉 sync），
    //   否则量出来的「读入耗时」根本不是它们的读入耗时 ——
    //   第 32 章那条「两份代码的 I/O 设置要一致」正是这么栽的。
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (ioOnly) { printf("只读入：n = %d, k = %d\n", n, k); return 0; }

    long long pushes = 0, backPops = 0, frontPops = 0, tests = 0;
    deque<int> q;
    for (int i = 1; i <= n; i++) {
        while (true) {
            tests++;
            if (q.empty() || a[q.back()] < a[i]) break;
            q.pop_back(); backPops++;
        }
        q.push_back(i); pushes++;
        if (q.front() <= i - k) { q.pop_front(); frontPops++; }
    }

    printf("n = %d，k = %d\n\n", n, k);
    printf("%s%s\n", padDisp("写法", 34).c_str(), "碰数据的次数");
    printf("%s\n", string(52, '-').c_str());
    printf("%s%lld\n", padDisp("★ 单调队列：入队", 34).c_str(), pushes);
    printf("%s%lld\n", padDisp("★ 单调队列：队尾出队", 34).c_str(), backPops);
    printf("%s%lld\n", padDisp("★ 单调队列：队头出队（滑出窗口）", 34).c_str(), frontPops);
    printf("%s%lld\n", padDisp("   单调队列：while 判断", 34).c_str(), tests);
    printf("%s%lld\n", padDisp("   每个窗口扫一遍（winBrute）", 34).c_str(),
           (long long)(n - k + 1) * k);
    printf("\n★ 入队恒等于 n = %d，出队 %lld 次（队尾 + 队头）≤ n —— 和 k 一点关系都没有。\n",
           n, backPops + frontPops);
    printf("  而暴力那一行是 (n−k+1)·k，k 一拧就炸。这就是 O(n) 和 O(nk) 的全部差别。\n");
    return 0;
}

// 滑动窗口 —— 把单调队列**每一步**的队列内容打出来（动画照着这张表画）
//
// 这份代码为什么存在：和 trace.cpp 一样，check:viz 拿它和网页动画**逐行**对 ——
// 只比最终答案的话，「答案蒙对、过程画错」根本发现不了。
//
// 每一步打四样：
//   · 队尾弹了几个（因为「又老又不如新来的」）
//   · 队头弹了几个（因为**滑出窗口**了）—— ★ 这一列是单调队列比单调栈多出来的那一头
//   · 队列里剩哪些**下标**
//   · 这一格的窗口最小值（i < k 时还没有完整窗口，打「—」）
//
// ⚠ cout / printf 混用，不能关 sync（第 26 章那条）。
//
// 输入：同 winBrute.cpp（只演示最小值那一半）

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

static string padDisp(const string& s, int width) {
    int disp = 0;
    for (size_t i = 0; i < s.size();) {
        unsigned char c = s[i];
        if (c < 0x80) { disp += 1; i += 1; }
        else if ((c >> 5) == 6) { disp += 1; i += 2; }
        else if ((c >> 4) == 14) { disp += 2; i += 3; }
        else { disp += 2; i += 4; }
    }
    return s + string(max(0, width - disp), ' ');
}

int main() {
    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    printf("%s%s%s%s%s%s\n",
           padDisp("步", 6).c_str(), padDisp("新来", 9).c_str(),
           padDisp("队尾弹", 9).c_str(), padDisp("队头弹", 9).c_str(),
           padDisp("队列里的下标", 20).c_str(), "窗口最小值");
    printf("%s\n", string(70, '-').c_str());

    deque<int> q;
    long long pushes = 0, backPops = 0, frontPops = 0;
    for (int i = 1; i <= n; i++) {
        int b = 0, f = 0;
        while (!q.empty() && a[q.back()] >= a[i]) { q.pop_back(); b++; backPops++; }
        q.push_back(i); pushes++;
        if (q.front() <= i - k) { q.pop_front(); f++; frontPops++; }

        string body;
        for (int x : q) { if (!body.empty()) body += " "; body += to_string(x); }
        string ansCol = (i >= k) ? to_string(a[q.front()]) : "—";
        printf("%s%s%s%s%s%s\n",
               padDisp("步 " + to_string(i), 6).c_str(),
               padDisp("a=" + to_string(a[i]), 9).c_str(),
               padDisp(to_string(b) + " 个", 9).c_str(),
               padDisp(to_string(f) + " 个", 9).c_str(),
               padDisp("[" + body + "]", 20).c_str(), ansCol.c_str());
    }

    printf("%s\n", string(70, '-').c_str());
    printf("★ 入队 %lld 次；出队 %lld 次（队尾 %lld + 队头 %lld），还剩 %zu 个在队里没人赶 ——\n"
           "  每个下标**至多**进出各一次，这就是全部。\n",
           pushes, backPops + frontPops, backPops, frontPops, q.size());
    cout << "★ 两个 while 加起来转不过 2n 圈，所以它是 O(n) —— 和单调栈是同一句话，"
            "只是多管了一头。\n";
    return 0;
}

// 多重背包 O(nW)：单调队列优化 —— ★ 还第 24 章欠下的那笔账
//
// 这份代码为什么存在：第 24 章讲完二进制拆分（O(W × Σlog k)）之后，
// 章末白纸黑字写着「还能做到 O(nW)，等第 35 章讲完单调队列再回来收尾」。这就是收尾。
//
// ★ 关键一步只有一句话：**把那个 max 写出来，它就是一个滑动窗口最大值。**
//
// 多重背包的转移是（第 i 种物品，价值 v、重量 w、至多 k 件）：
//
//     f[j] = max_{0 ≤ t ≤ k}  f[j − t·w] + t·v
//
// 右边只用到 `j, j−w, j−2w, …` —— **下标模 w 同余的那一串**，彼此谁也够不着谁。
// 于是把容量按 `j mod w` 分成 w 组，每组单独看。设 `j = r + s·w`，令 `g[s] = f[r + s·w]`：
//
//     g[s] = max_{0 ≤ t ≤ k}  g[s − t] + t·v
//          = max_{s−k ≤ s' ≤ s} ( g[s'] − s'·v ) + s·v          ← 把 t 换成 s' = s − t
//
// ★ 括号里那一坨**只和 s' 有关**，s·v 提得出去 ——
//   于是它就是「在 `g[s'] − s'·v` 这个序列上，求一个宽度 k+1 的滑动窗口最大值」，
//   正是这一章前半章那道题。每个容量只被处理一次 → **O(nW)**。
//
// ⚠ 这里有一个非写不可的细节：队列里必须存**算好的那个值**，不能存下标之后回头去读 `f`——
//   因为 `f[r + s·w]` 在这一行就被覆盖掉了。**读要在写之前**（代码里 val 那一行）。
//   ★ 这和第 23 章「一维倒序」是同一个毛病的两种解法：那边靠倒序避开「读到本轮写过的」，
//   这边靠「先读进队列」避开。**转移的读写次序，从来都是 DP 的一部分。**
//
// ⚠ 那个「提出去的 s·v」也解释了为什么单调队列要存下标：
//   队列里比的是 `g[s'] − s'·v`（去掉 s·v 之后的**可比量**），
//   而窗口边界 `s − k` 是拿**下标**判的。★ 值用来比大小，下标用来判出没出窗口 —— 两件事。
//
// 对拍：和第 24 章的 multi.cpp（二进制拆分）、multiBrute.cpp（DFS 枚举每种拿几件）
//       用**同一个生成器** `code/24-knapsack-multi/multiGen.cpp` 逐字节比。
//       ★ 这是本教材第二次**跨章节交叉验证**（第一次是第 30 章把第 13 章那张网格图转成图跑）。
//
// 输入输出同 code/24-knapsack-multi/multiBrute.cpp：
//   第一行 n W；接下来 n 行每行 v w k

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

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

    int n;
    long long W;
    if (!(cin >> n >> W)) return 0;

    vector<long long> f(W + 1, 0);
    for (int i = 0; i < n; i++) {
        long long v, w, k;
        cin >> v >> w >> k;
        if (w <= 0) continue;                       // 重量为 0 的物品没有「窗口」可言
        if (k > W / w) k = W / w;                   // 装不完那么多，截断（不截也对，只是白转）

        for (long long r = 0; r < w && r <= W; r++) {
            // 这一组的容量是 r, r+w, r+2w, …；s 是它在组里的编号
            deque<pair<long long, long long>> q;    // (s, f_旧[r+s·w] − s·v)
            for (long long s = 0; r + s * w <= W; s++) {
                long long val = f[r + s * w] - s * v;        // ★ 读要在写之前
                while (!q.empty() && q.back().second <= val) q.pop_back();
                q.push_back({s, val});
                if (q.front().first < s - k) q.pop_front();   // 出了宽度 k+1 的窗口
                f[r + s * w] = q.front().second + s * v;
            }
        }
    }

    cout << f[W] << "\n";
    return 0;
}

// 柱状图里最大的矩形 —— 正解：单调栈 O(n)
//
// 这份代码为什么存在：它是本章的主角。
//
// ★ 换一个问法就全通了：**以第 t 根柱子的高度为高**的最大矩形，宽能有多少？
//   往左能扩到「左边第一根**比它矮**的柱子」的右边，往右扩到「右边第一根比它矮的」的左边。
//   于是问题变成：**对每一根柱子，求出它左右两侧第一个更矮的柱子在哪。**
//   （★ 请注意：问的是**位置**，不是值 —— 所以栈里存的必须是**下标**。）
//
// 单调栈就是干这个的：栈里的下标，对应的高度**从栈底到栈顶严格递增**。
//   新来一根 cur，把栈顶所有「不比 cur 矮」的都弹掉 ——
//   对每个被弹出的 t，此刻的两件事同时揭晓：
//     · 右边第一个比它矮的，就是**当前这个 i**；
//     · 左边第一个比它矮的，就是**它被弹掉之后的新栈顶**（因为栈里是递增的）。
//   所以宽 = i − 新栈顶 − 1（★ 那个 −1 是「不含两端那两根更矮的」，wrongWidth.cpp 就错在这里）。
//
// ★★ 关键一步是**均摊分析**：这里明明有两层循环（for 里套 while），但它是 O(n) ——
//   因为每根柱子**一辈子只入栈一次、只出栈一次**，那句 while 转的总次数不会超过 n。
//   这和第 7 章双指针「两个指针都只往前走，所以是 O(n)」是同一件事。
//   count.cpp 把这两个次数数出来给你看。
//
// ⚠ 末尾那根 −1 的哨兵：扫完之后栈里通常还剩一串（越往栈顶越高），
//   它们的右边界还没揭晓。放一根「比所有柱子都矮」的哨兵，就能把它们全逼出来，
//   主循环一个字都不用改。忘了这件事就是 wrongTail.cpp。
//   ⚠ 为什么写 −1 而不是 0：题目允许 h = 0，写 −1 才**严格**比所有柱子矮，一句话就说得清。
//   （这道题写 0 其实也对 —— 高 0 的柱子面积也是 0，漏算了也不影响最大值 ——
//    但那要多想一步。★ 哨兵的意义就是「不用多想一步」，别给自己留这种账。）
//
// 输入输出同 brute.cpp。

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

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

    int n;
    if (!(cin >> n)) return 0;
    vector<long long> h(n + 2);
    for (int i = 1; i <= n; i++) cin >> h[i];
    h[n + 1] = -1;                       // 哨兵：比任何柱子都矮，把栈里剩下的全逼出来

    long long ans = 0;
    vector<int> st;                      // ★ 存的是**下标**，对应高度严格递增
    st.reserve(n + 1);

    for (int i = 1; i <= n + 1; i++) {
        while (!st.empty() && h[st.back()] >= h[i]) {
            int t = st.back();
            st.pop_back();
            long long left = st.empty() ? 0 : st.back();   // 左边第一个比 h[t] 矮的下标（没有就当 0）
            long long w = i - left - 1;
            ans = max(ans, h[t] * w);
        }
        st.push_back(i);
    }

    cout << ans << "\n";
    return 0;
}

// 滑动窗口最值 —— 正解：单调队列 O(n)
//
// 这份代码为什么存在：它是本章后半章的主角，也是**均摊分析的第二次登场**。
//
// ★ 关键一步和单调栈是同一句话，只是多了一头：
//   队列里存**下标**，对应的值单调（求最小值时递增）。
//   · **队尾**：新来一个 a[i]，把队尾所有「不比它小」的都弹掉 ——
//     理由是那些家伙**又老又大**，只要 a[i] 还在窗口里，它们永远轮不到当最小值。
//   · **队头**：如果队头那个下标已经滑出窗口（≤ i−k），弹掉。
//     ★ **这就是为什么队列里必须存下标**：光存值，你根本不知道它是什么时候进来的
//     （winWrongVal.cpp 就死在这里）。
//   于是队头永远是当前窗口的最小值，O(1) 取到。
//
// ★★ 还是均摊：每个下标**只入队一次、只出队一次**（要么被队尾挤掉、要么从队头滑走），
//   所以两个 while 加起来转不过 2n 圈。和单调栈、和第 7 章双指针，是同一件事的三张脸。
//
// ⚠ 单调栈和单调队列的区别只有一句：**单调栈只从一头进出，单调队列两头都要动** ——
//   多出来的那一头，管的正是「窗口有多宽」这件事。
//
// 输入输出同 winBrute.cpp。

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

/** wantMin = true 求每个窗口的最小值，false 求最大值 —— 两者只差一个不等号方向 */
static void solve(const vector<long long>& a, int n, int k, bool wantMin) {
    deque<int> q;                                     // ★ 存下标，不存值
    for (int i = 1; i <= n; i++) {
        // ① 队尾：把「又老又不如新来的」全弹掉
        while (!q.empty() && (wantMin ? a[q.back()] >= a[i] : a[q.back()] <= a[i]))
            q.pop_back();
        q.push_back(i);
        // ② 队头：滑出窗口的弹掉（一次最多滑出一个，所以 if 就够）
        if (q.front() <= i - k) q.pop_front();
        // ③ 从第 k 个数开始，每一格都有一个完整的窗口
        if (i >= k) cout << a[q.front()] << " \n"[i == n];
    }
}

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

    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    solve(a, n, k, true);
    solve(a, n, k, false);
    return 0;
}