#include<bits/stdc++.h>
using namespace std;
int h[5000001],h1[1000001],len1,b,c,n,m,s,x,t,u,v,len;
void up(int x){
	while(x!=1&&h[x]<h[x/2])
	{
		swap(h[x],h[x/2]);
		x/=2;
	}
}
void down(int x){
	while(h[x]>h[2*x]&&2*x<=len||h[x]>h[2*x+1]&&2*x+1<=len)
	{
		if(2*x+1>len)
		{
			swap(h[x],h[2*x]);
			x*=2;
		}
		else
		{
			if(h[x*2]<h[x*2+1])
			{
				swap(h[x],h[2*x]);
				x*=2;
			}
			else
			{
				swap(h[x],h[x*2+1]);
				x=2*x+1;
			} 
		}
	}
}

void up1(int x){
	while(x!=1&&h[x]>h[x/2])
	{
		swap(h[x],h[x/2]);
		x/=2;
	}
}
void down1(int x){
	while(h1[x]<h1[2*x]&&2*x>=len||h1[x]>h1[2*x+1]&&2*x+1>=len)
	{
		if(2*x+1<len)
		{
			swap(h1[x],h1[2*x]);
			x*=2;
		}
		else
		{
			if(h1[x*2]>h1[x*2+1])
			{
				swap(h1[x],h1[2*x]);
				x*=2;
			}
			else
			{
				swap(h1[x],h1[x*2+1]);
				x=2*x+1;
			} 
		}
	}
}
int main(){
    cin>>n;
    for(int i=1,op,x;i<=n;i++){
    	cin>>x;
    	len1++;
    	h1[len1]=x;
    	up1(len1);
	    if(i%2==1)
	    {
	    	while(len1&&len&&h1[1]>h[1])
	       {
	           len++;
	           h[len]=h1[i];
	           up(len);
	           
	           swap(h1[1],h1[len1]);
	           len1--;
	           down1(1);
	       }
	       while(len1>len)
	       {
	           len++;
	           h[len]=h1[i];
	           up(len);
	           
	           swap(h1[1],h1[len1]);
	           len1--;
	           down1(1);
	       }
	       while(len1>len-1)
	       {
	           len++;
	           h[len]=h1[i];
	           up(len);
	           
	           swap(h1[1],h1[len1]);
	           len1--;
	           down1(1);
	       }
	       	    cout<<h[1]<<endl;
	    }
	}
    return 0;
}