#include<stdio.h>
#include<iostream>
using namespace std;
const long long maxn=100005;
struct priority_queue//小根堆 
{
	long long len;
	long long a[maxn];
	void init()
	{
		len=0;
	}
	void push_up(long long t)
	{
		if(t==1)	return ;
		long long fa=t/2;
		if(a[fa]<a[t])	return ;
		
		long long kkk=a[t];
		a[t]=a[fa];
		a[fa]=kkk;
		
		push_up(fa);
	}
	void put_down(long long t)
	{
		if(t*2>len)	return ;
		long long son=t*2;
		if(a[son]>a[son+1])	son++;
		if(a[t]>a[son])
		{
			long long kkk=a[t];
			a[t]=a[son];
			a[son]=kkk;
			put_down(son);
		}
		else	return ;
	}
	void push(long long x)
	{
		len++;
		a[len]=x;
		push_up(len);
	}
	void pop()
	{
		long long kkk=a[1];
		a[1]=a[len];
		len--;
		put_down(1);
	}
	long long top(){return a[1];}
};
int main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);
	priority_queue q;
	q.init();
	long long n;
	cin>>n;
	for(long long i=1;i<=n;i++)
	{
		long long m;
		cin>>m;
		q.push(m);
		if(i%2==1)
		{
			cout<<q.a[i/2+1]<<"\n";
		}
	}
	return 0;
}