#include<bits/stdc++.h>
using namespace std;
int b[50001],s[50001],lens,lenb;	//b[]大顶堆，s[]小顶堆
void addb(int t)
{
	int q;
	b[++lenb]=t;
	q=lenb;
	while(q>1)
	{
		if(b[q]>b[q/2]) 
		{
			swap(b[q],b[q/2]);
			q/=2;
		}
		else break;
	}
}
void adds(int t)
{
	int q;
	s[++lens]=t;
	q=lens;
	while(q>1)
	{
		if(s[q]<s[q/2]) 
		{
			swap(s[q],s[q/2]);
			q/=2;
		}
		else break;
	}
}
void db()			//删堆顶
{
	if(lenb==0) return;
	b[1]=b[lenb--];
	int p=1;
	while(1)
	{
		int maxp=p;
		if(b[2*p]>b[maxp]&&2*p<=lenb) maxp=2*p;
		if(b[2*p+1]>b[maxp]&&2*p+1<=lenb) maxp++;
		if(p==maxp) break;
		swap(b[maxp],b[p]);
		p=maxp;
	}
}
void ds()		//删堆顶
{
	if(lens==0) return;
	s[1]=s[lens--];
	int p=1;
	while(1)
	{
		int minp=p;
		if(s[2*p]<s[minp]&&2*p<=lens) minp=2*p;
		if(s[2*p+1]<s[minp]&&2*p+1<=lens) minp++;
		if(p==minp) break;
		swap(s[minp],s[p]);
		p=minp;
	}
}
int main()
{
	int n,t1,t2;
	cin>>n>>t1;
	cout<<t1<<endl;
	b[1]=t1;
	lenb=1;
	for(int i=1;i<n-1;i+=2)
	{	
		cin>>t1>>t2;
		if(t1<=b[1]) addb(t1);
		else adds(t1);
		if(t2<=b[1]) addb(t2);
		else adds(t2);
		if(lens>lenb+1)
		{
			int x=s[1];
			ds();
			addb(x);
		}
		if(lens<lenb-1)
		{
			int x=b[1];
			db();
			adds(x);
		}
		if(lenb>lens) cout<<b[1]<<endl;
		else cout<<s[1]<<endl;
	}
	return 0;
 }