#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int n,x;
priority_queue<int,vector<int>,greater<int>>h1;
priority_queue<int>h2;
int FastReadInt()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
		{
			f=-1;
		}
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<1)+(x<<3)+(c^48),c=getchar();
	}
	return x*f;
}
int main(){
	n=FastReadInt();
	for(int i=1;i<=n;i++)
	{
		x=FastReadInt();
		if(h1.empty())
		{
			h1.push(x);
		}
		else if(x>=h1.top())
		{
			h1.push(x);
		}
		else
		{
			h2.push(x);
		}
		if(i%2)
		{
			while(h1.size()>i/2+1)
			{
				h2.push(h1.top());
				h1.pop();
			}
			while(h1.size()<i/2+1)
			{
				h1.push(h2.top());
				h2.pop();
			}
			printf("%d\n",h1.top());
		}
	}
	return 0;
}