#include <iostream> #include <bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 2*1e5+5, INF = 4e18+9; struct normalize{ vector<ll> poi, pot; void add(ll x){ poi.push_back(x); } void start(){ sort(poi.begin(), poi.end()); if(poi.size() > 0) pot.push_back(poi[0]); for(int i = 1; i < (int)poi.size(); i++){ if(poi[i] != poi[i-1]){ pot.push_back(poi[i]); } } } int encode(ll x){ return lower_bound(pot.begin(), pot.end(), x) - pot.begin()+1; } }; struct DSU{ int n; vector<int> pa, sz; DSU(int n) : n(n){ pa.resize(n+1); sz.resize(n+1, 1); for(int i = 0; i <= n; i++){ pa[i] = i; } }; int find(int x){ while(x != pa[x]){ x = pa[x] = pa[pa[x]]; } return x; } bool same(int x, int y){ return find(x) == find(y); } bool merge(int x, int y){ x = find(x); y = find(y); if(x == y) return false; pa[y] = x; sz[x] += sz[y]; return true; } int size(int x){ return sz[find(x)]; } }; void solve(){ int n; cin >> n; vector<int> a(n+1); normalize norm; for(int i = 1; i <= n; i++){ cin >> a[i]; norm.add(a[i]); } norm.start(); for(int i = 1; i <= n; i++){ a[i] = norm.encode(a[i]); } vector<int> d(n+1, 0); DSU dsu(n+1); vector<int> v; for(int i = 1; i <= n; i++){ if(d[a[i]] == 0){ //d[a[i]]++; //continue; } int j = dsu.find(i-1); v.clear(); v.push_back(i); while(j >= 1){ v.push_back(j); if(a[j] == a[i]){ for(int it = 1; it < (int)v.size(); it++){ int x = v[it]; dsu.merge(j, x); d[a[x]] -= v[it-1] - x; } dsu.merge(j, i); d[a[i]] += i - j; break; } j = dsu.find(j - 1); } d[a[i]]++; } for(int i = 1; i <= n; i++){ int j = dsu.find(i); cout << a[j] << "\n"; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); }