#include<bits/stdc++.h>
using namespace std;
int n,a[100001],b[100001];
struct node {
	int l,r,sum;
} tree[400001];
struct ckid {
	int sit,dat;
} v[100001];
bool cmp(ckid x,ckid y) {
	return x.dat<y.dat;
}
void build(int left,int right,int pos) {
	tree[pos].l=left;
	tree[pos].r=right;
	if(left==right)return;
	int mid=(left+right)/2;
	build(left,mid,pos*2);
	build(mid+1,right,pos*2+1);
}
void tplus(int pos,int goal,int cnt) {
	if(tree[pos].l==tree[pos].r) {
		if(tree[pos].l==goal)tree[pos].sum+=cnt;
		return;
	}
	int mid=(tree[pos].l+tree[pos].r)/2;
	if(goal<=mid) tplus(pos*2,goal,cnt);
	if(goal>mid) tplus(pos*2+1,goal,cnt);
	tree[pos].sum=tree[pos*2].sum+tree[pos*2+1].sum;
}
int middle(int pos,int cnt,int sum) {
	if(tree[pos].l==tree[pos].r)return tree[pos].l;
	cnt+=tree[pos*2].sum;
	if(cnt>=(sum+1)/2)return middle(pos*2,0,sum);
	else return middle(pos*2+1,cnt,sum);
}
void dick() {
	sort(v+1,v+n+1,cmp);
	for(int i=1; i<=n; i++) {
		a[v[i].sit]=i;
		b[i]=v[i].dat;
	}
}
int main() {
	cin>>n;
	for(int i=1; i<=n; i++) {
		cin>>v[i].dat;
		v[i].sit=i;
	}
	dick();
	build(1,n,1);
	cout<<b[a[1]]<<endl;
	tplus(1,a[1],1);
	for(int i=2; i<=n; i++) {
		tplus(1,a[i],1);
		if(i%2==1)cout<<b[middle(1,0,i)]<<endl;
	}
}

用权值线段树做的。。。(萌新刚学，轻喷)