#include<bits/stdc++.h>
using namespace std;
int n,a[100010],x;
priority_queue<int> pmx; // 符号+  比中位数小或等于的数
priority_queue<int> pmi; // 符号-  比中位数大于的数
int main(){
    cin >> n;
    for(int i=1;i<=n;i++)cin >>a[i];
    cout << a[1] << endl;pmx.push(a[1]); // 先处理第一个数
    for(int i=3;i<=n;i+=2){
        for(int j=1;j>=0;j--){ // 每次处理两个
            if(pmi.size()==0) x = pmx.top();
            else x = -pmi.top(); // 防止堆中无元素导致错误

            if(x<a[i-j])pmi.push(-a[i-j]); // 添加元素
            else pmx.push(a[i-j]);
        }
        // 将两个堆的长度差减小
        while(pmx.size()>pmi.size()+1){
            pmi.push(-pmx.top());
            pmx.pop();
        }
        while(pmx.size()<=pmi.size()){
            pmx.push(-pmi.top());
            pmi.pop();
        }
        cout << pmx.top() << endl; // 输出
    }
    return 0;
}