#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<ll, int> Pl;
const double PI = 3.1415926535897932;   // acos(-1)
const double EPS = 1e-15;
const int INF = 1001001001;
const ll mod = 1e+9 + 7;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define chadd(x, y) x = (x + y) % mod

template<typename Monoid>
struct SegmentTree{
    using F = function<Monoid(Monoid, Monoid)>;

    int sz;
    vector<Monoid> seg;

    const F f;      // モノイドに対して二項演算を行う関数オブジェクト
    const Monoid M1;

    SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1){
        sz = 1;
        while(sz < n)   sz <<= 1;
        seg.assign(2 * sz, M1);
    }

    void set(int k, const Monoid &x){
        seg[k + sz] = x;
    }

    void build(){
        for(int k = sz - 1; k > 0; --k){
            seg[k] = f(seg[k << 1], seg[k << 1 | 1]);
        }
    }

    void update(int k, const Monoid &x){
        k += sz;
        seg[k] = x;
        while(k >>= 1){
            seg[k] = f(seg[k << 1], seg[k << 1 | 1]);
        }
    }

    Monoid query(int a, int b){
        Monoid L = M1, R = M1;
        for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){
            if(a & 1)   L = f(L, seg[a++]);
            if(b & 1)   R = f(seg[--b], R);
        }
        return f(L, R);
    }

    Monoid operator[](const int &k) const{
        return seg[k + sz];
    }
};

template<typename T>
struct Compress{
    vector<T> xs;
    Compress() = default;
    Compress(const vector<T> &vs){
        add(vs);
    }
    Compress(const initializer_list<vector<T>> &vs){
        for(auto &p : vs)   add(p);
    }
    void add(const vector<T> &vs){
        copy(begin(vs), end(vs), back_inserter(xs));
    }
    void add(const T &x){
        xs.emplace_back(x);
    }
    void build(){
        sort(begin(xs), end(xs));
        xs.erase(unique(begin(xs), end(xs)), end(xs));
    }
    vector<int> get(const vector<T> &vs) const{
        vector<int> ret;
        transform(begin(vs), end(vs), back_inserter(ret), [&](const T &x){
            return lower_bound(begin(xs), end(xs), x) - begin(xs);
        });
        return ret;
    }
    int get(const T &x) const{
        return lower_bound(begin(xs), end(xs), x) - begin(xs);
    }
    const T &operator[](int k) const{
        return xs[k];
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> x(n);
    for(int i = 0; i < n; ++i)  cin >> x[i];
    Compress<int> c(x);
    c.build();
    SegmentTree<int> seg(n, [](int a, int b){return a + b;}, 0);
    for(int i = 0; i < n; ++i){
        int hoge = c.get(x[i]);
        seg.update(hoge, seg[hoge] + 1);
    }

    for(int i = 0; i < n; ++i){
        int hoge = c.get(x[i]);
        seg.update(hoge, seg[hoge] - 1);
        int lb = 0, ub = n;
        int sum = n / 2;
        while(ub - lb > 1){
            int mid = (lb + ub) / 2;
            if(seg.query(0, mid) < sum) lb = mid;
            else    ub = mid;
        }
        cout << c[lb] << "\n";
        seg.update(hoge, seg[hoge] + 1);    
    }
}

Measured memory_bytes: 6004