#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// seg: start -> (end, color)
map<int, pair<int, ll>> seg;
// color -> set of (start, end) ordered by start
unordered_map<ll, set<pair<int,int>>> colorSegs;
// helper: add segment [l,r] with color c
void addSeg(int l, int r, ll c) {
seg[l] = {r, c};
colorSegs[c].insert({l, r});
}
// helper: erase segment by iterator in seg
void eraseSegByIt(map<int, pair<int,ll>>::iterator it) {
int l = it->first;
int r = it->second.first;
ll c = it->second.second;
auto &S = colorSegs[c];
S.erase({l, r});
seg.erase(it);
}
// helper: find the segment containing position pos, or seg.end()
map<int, pair<int,ll>>::iterator findContaining(int pos) {
auto it = seg.upper_bound(pos);
if (it == seg.begin()) return seg.end();
--it;
int l = it->first;
int r = it->second.first;
if (l <= pos && pos <= r) return it;
return seg.end();
}
// split segment that contains pos into [l,pos-1] and [pos,r]
// returns iterator to the segment that starts at pos (the right piece).
// if pos not inside any segment, returns seg.end()
// if pos already equal to segment start, returns iterator to that segment
map<int, pair<int,ll>>::iterator split(int pos) {
auto it = findContaining(pos);
if (it == seg.end()) return seg.end();
int l = it->first;
int r = it->second.first;
ll c = it->second.second;
if (l == pos) return it;
// split: remove old, insert left and right parts
// erase from color set
colorSegs[c].erase({l, r});
seg.erase(it);
// left part [l, pos-1]
seg[l] = {pos - 1, c};
colorSegs[c].insert({l, pos - 1});
// right part [pos, r]
seg[pos] = {r, c};
colorSegs[c].insert({pos, r});
return seg.find(pos);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
if (!(cin >> N)) return 0;
vector<ll> A(N+1);
for (int i = 1; i <= N; ++i) cin >> A[i];
// process stones 1..N
for (int i = 1; i <= N; ++i) {
ll c = A[i];
// find rightmost occurrence j of color c among positions < i
int j = -1;
auto itColor = colorSegs.find(c);
if (itColor != colorSegs.end() && !itColor->second.empty()) {
// last element in set has largest start, its second is end
auto last = *prev(itColor->second.end());
j = last.second; // end index of last segment of color c
}
// if there's a previous occurrence, paint [j+1, i-1] to c
if (j != -1 && j + 1 <= i - 1) {
int L = j + 1, R = i - 1;
// split on L and i (so boundaries align)
auto itL = split(L);
// split(i) might return seg.end() if i is outside current coverage,
// which is fine. We want iterator to first start >= i as end boundary.
split(i); // ensures any segment crossing i is cut so lower_bound(i) is correct
auto itR = seg.lower_bound(i); // first segment start >= i
// collect starts to delete between [itL, itR)
vector<int> toDel;
for (auto it = itL; it != itR; ++it) {
toDel.push_back(it->first);
}
for (int s : toDel) {
auto itRem = seg.find(s);
if (itRem != seg.end()) eraseSegByIt(itRem);
}
// insert the combined new segment [L, R] with color c
addSeg(L, R, c);
}
// insert single stone [i,i] with color c
addSeg(i, i, c);
// try to merge with previous
auto it = seg.find(i);
if (it != seg.begin()) {
auto pit = it;
--pit;
// if adjacent and same color
if (pit->second.first + 1 == it->first && pit->second.second == it->second.second) {
int nl = pit->first;
int nr = it->second.first;
ll cc = it->second.second;
// erase both
eraseSegByIt(pit);
eraseSegByIt(seg.find(i)); // it might be invalidated, find again by start nl? safer find
// insert merged
addSeg(nl, nr, cc);
it = seg.find(nl);
}
}
// try to merge with next
if (!seg.empty()) {
// refresh it (find the segment that contains i or that starts <= i)
auto it2 = seg.upper_bound(i);
if (it2 != seg.begin()) {
--it2;
if (it2->first <= i && it2->second.first >= i) {
auto cur = it2;
auto nit = next(cur);
if (nit != seg.end()) {
if (cur->second.first + 1 == nit->first && cur->second.second == nit->second.second) {
int nl = cur->first;
int nr = nit->second.first;
ll cc = cur->second.second;
eraseSegByIt(cur);
// after erasing cur, nit's iterator invalidated; find nit by start
eraseSegByIt(seg.find(nit->first));
addSeg(nl, nr, cc);
}
}
}
}
}
}
// build final answer by iterating segments
vector<ll> ans(N+1);
for (auto &pr : seg) {
int l = pr.first;
int r = pr.second.first;
ll c = pr.second.second;
for (int i = l; i <= r; ++i) ans[i] = c;
}
// print
for (int i = 1; i <= N; ++i) cout << ans[i] << "\n";
return 0;
}
