rt

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,x;
	set<int> a,b;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		if(b.size()==0)
		    b.insert(x);
		else if(a.size()!=0)
		{
		    if(x<=*a.rbegin())
		        a.insert(x);
		    else
		        b.insert(x);
		}
		else
		    b.insert(x);
		if(a.size()>b.size())
		{
			b.insert(*a.rbegin());
			a.erase(*a.rbegin());
		}
		else if(b.size()-a.size()>1)
		{
			a.insert(*b.begin());
			b.erase(*b.begin());
		}
		if(i%2)
		{
		    cout<<*b.begin()<<endl;
		}
	}
    return 0;
}