#include using namespace std; using ll = long long; #ifdef LOCAL #include #else #define debug(...) #endif template struct Intervals { static constexpr S INF = numeric_limits::max() / 2; static constexpr S L = -INF, R = INF; T none_val; int total_num; // none_val でない区間の個数 S total_len; // none_val でない区間の長さの合計 map data; // コンストラクタ:全体 [L, R) を none_val に初期化 Intervals(T nv = -1) : none_val(nv), total_num(0), total_len(0) { data.emplace(L, none_val); data.emplace(R, none_val); } // 区間 [l, r) の値を v に設定 void set(S l, S r, T v) { assert(L <= l && r < R); if (l >= r) return; auto it_l = split(l), it_r = split(r); // [l, r) に含まれる既存の区間をすべて削除 for (auto it = it_l; it != it_r;) { if (it->second != none_val) { S seg_l = it->first, seg_r = next(it)->first; total_len -= (seg_r - seg_l); total_num--; } it = data.erase(it); } // 新たに [l, r) を挿入 auto it = data.emplace(l, v).first; if (v != none_val) { total_len += (r - l); total_num++; } // 左側との結合 if (it != data.begin()) { auto it_prev = prev(it); if (it_prev->second == v) { data.erase(it); total_num--; l = it_prev->first; it = it_prev; } } // 右側との結合 auto it_next = next(it); if (it_next != data.end() && it_next->second == v) { data.erase(it_next); total_num--; } } // 点 i が含まれる [i, i + 1) の値を返す T get_value(S i) { assert(L <= i && i < R); auto it = prev(data.upper_bound(i)); return it->second; } // 点 i が含まれる区間 [l, r) とその値 v を返す tuple get(S i) { assert(L <= i && i < R); auto it_r = data.upper_bound(i), it_l = prev(it_r); return make_tuple(it_l->first, it_r->first, it_l->second); } // 区間 [l, r) 内の区間を(境界ごとに分割した) run-length 圧縮結果として返す vector> get(S l, S r) { assert(L <= l && r < R); vector> res; if (l >= r) return res; auto it_r = data.upper_bound(l), it_l = prev(it_r); while (it_l->first < r) { res.emplace_back(max(l, it_l->first), min(it_r->first, r), it_l->second); it_l = it_r++; } return res; } private: // 点 pos において区間を分割し,すでに境界があればその位置のイテレータを返す // そうでなければ,その区間 [l, r) を [l, pos) と [pos, r) に分割し,後者の先頭を返す typename map::iterator split(S pos) { auto it = data.lower_bound(pos); if (it != data.end() && it->first == pos) return it; T v = prev(it)->second; auto res = data.emplace(pos, v).first; if (v != none_val) total_num++; return res; } }; template vector compress(vector& v) { vector res(v); sort(res.begin(), res.end()); res.erase(unique(res.begin(), res.end()), res.end()); for (auto&& elem : v) elem = lower_bound(res.begin(), res.end(), elem) - res.begin(); return res; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); int N; cin >> N; vector A(N); for (int i = 0; i < N; i++) cin >> A[i]; auto comp = compress(A); int M = comp.size(); vector> P(M); for (int i = 0; i < N; i++) P[A[i]].emplace(i); Intervals I; for (int i = 0; i < M; i++) { if (P[i].empty()) continue; int l = *P[i].begin(), r = *P[i].rbegin(); // [l, r] を comp[i] に設定 I.set(l, r + 1, comp[i]); } vector B(N); for (auto [l, r, v] : I.get(0, N)) { for (int i = l; i < r; i++) B[i] = v; } for (int i = 0; i < N; i++) { cout << B[i] << " \n"[i == N - 1]; } }