// Algorithm: Same as the C version. Components are contiguous; a cut sits where
// prefix-max meets suffix-min with prefMax[i] <= sufMin[i+1]. One sweep with a
// running max M; on each cut, write M into ans[left..i] and reset.
// 演算法同 C 版本：用前綴最大與後綴最小定位切點，分量內每格答案都是該段最大。

#include <vector>     // std::vector 動態陣列 / dynamic array container
#include <algorithm>  // std::min, std::max

class Solution {
public:
    std::vector<int> maxValue(std::vector<int>& nums) {
        int n = static_cast<int>(nums.size());               // 取陣列長度，轉成 int 比較好用 / cast size to int for index math
        std::vector<int> sufMin(n);                          // 後綴最小值陣列，長度 n / suffix-min array of length n

        sufMin[n - 1] = nums[n - 1];                         // 最右端的後綴最小是自己 / rightmost suffix min is itself
        for (int i = n - 2; i >= 0; --i) {                   // 從右往左填 / fill right-to-left
            // std::min 取兩數較小，較三元運算子更可讀 / std::min returns the smaller of two values
            sufMin[i] = std::min(nums[i], sufMin[i + 1]);
        }

        std::vector<int> ans(n);                             // 結果陣列，預設值 0 / result vector, default-initialised to 0
        int M = 0;                                           // 當前分量的前綴最大 / running prefix max in current group
        int left = 0;                                        // 當前分量的左端索引 / left boundary of current group
        for (int i = 0; i < n; ++i) {                        // 範圍迴圈也可，這裡需要索引 / index-based loop because we need i
            M = std::max(M, nums[i]);                        // 更新前綴最大 / update running max
            // 切點：i 是最後一個元素，或前綴最大 <= 後綴最小（左邊全部 <= 右邊全部，跨不過去）
            // Cut: end of array, or every left value <= every right value (no jump can bridge them).
            if (i == n - 1 || M <= sufMin[i + 1]) {
                for (int k = left; k <= i; ++k) {            // 把整段答案填成 M / write component max into the slice
                    ans[k] = M;
                }
                left = i + 1;                                // 下一段從 i+1 開始 / next component starts after the cut
                M = 0;                                       // 重置（nums[i] >= 1 故安全）/ reset (safe since nums[i] >= 1)
            }
        }
        return ans;                                          // vector 會自行管理記憶體 / vector handles its own memory
    }
};