CF547B AC

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
template <typename... Args> void logger(string vars, Args &&...values)
{
    cerr << vars << " = ";
    string delim = "";
    (..., (cerr << delim << values, delim = ", "));
    cerr << endl;
}

template <class T> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m)); }
template <class T> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n)); }
template <class T, T init> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m, init)); }
template <class T, T init> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n, init)); }

template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using vl = vector<ll>;
using vi = vector<int>;

int main(int argc, char **argv)
{
    int n;
    cin >> n;
    vi a(n);
    for (auto &x : a)
        cin >> x;

    vi sprev(n, -1), snext(n, n);
    stack<int> stck;
    for (int i = 0; i < n; ++i) {
        while (stck.empty() == false && a[stck.top()] >= a[i])
            stck.pop();
        sprev[i] = stck.empty() ? -1 : stck.top();
        stck.push(i);
    }
    while (stck.empty() == false)
        stck.pop();
    for (int i = n - 1; i >= 0; --i) {
        while (stck.empty() == false && a[stck.top()] >= a[i])
            stck.pop();
        snext[i] = stck.empty() ? n : stck.top();
        stck.push(i);
    }
    vi ans(n);

    /*
    dbg(n);
    for (int i = 0; i < n; ++i) {
        int x = a[i], sp = sprev[i], sn = snext[i];
        dbg(x, sp, sn);
    }
    vector<pii> as(n);
    for (int i = 0; i < n; ++i)
        as[i] = {1e9 - a[i], i};
    sort(as.begin(), as.end());

    for (int i = 0; i < n; ++i) {
        auto [val, idx] = as[i];
        val = 1e9 - val;
        int span = snext[idx] - sprev[idx] - 1;
        ans[span - 1] = max(ans[span - 1], val);
    }
    */
    for (int i = 0; i < n; ++i) {
        int span = snext[i] - sprev[i] - 1;
        ans[span - 1] = max(ans[span - 1], a[i]);
    }

    int prev = 0;
    for (int i = n - 1; i >= 0; i--)
        prev = max(prev, ans[i]), ans[i] = prev;
    for (auto x : ans)
        cout << x << ' ';
    cout << endl;
    return 0;
};