#include
#include
using namespace std;
priority_queuemaxheap;
priority_queue<int,vector,greater>minheap;
int median()
{
if(minheap.size()==maxheap.size())
{
return(minheap.top()+maxheap.top())/2;
}
if(minheap.size()>maxheap.size())
{
return minheap.top();
}
else return maxheap.top();
}
void runningstream(int d)
{
if(maxheap.size()==0)
{
maxheap.push(d);
return;
}
else if(d>maxheap.top() && minheap.size()==0)
{
minheap.push(d);
return;
}
else if(d<minheap.top())
{
maxheap.push(d);
if(maxheap.size()-minheap.size()>1)
{
int p = maxheap.top();
maxheap.pop();
minheap.push(p);
}
return;
}
else if(d>maxheap.top())
{
minheap.push(d);
if(minheap.size()-maxheap.size()>1)
{
int p = minheap.top();
minheap.pop();
maxheap.push(p);
}
return;
}
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int d;
cin>>d;
runningstream(d);
if(i>=2)
{
cout<<median()<<" ";
}
}
}