/dwd

#include<iostream> 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;
priority_queue<int,vector<int>,less<int> >Q; 
int n;
int a[100005];
int main(){
  scanf("%d",&n);
  for(int i=1;i<=n;i++){
  	cin>>a[i];
  }
  if(a[1]>a[2]){
  	Q.push(a[2]);
  	q.push(a[1]);
  }
  else{
  	Q.push(a[1]);
  	q.push(a[2]);
  }
  printf("%d\n",a[1]);
  if(n>=3){
  	Q.push(a[3]);
  	while(Q.top()>q.top()){
  		int tmp=Q.top();
  		Q.pop();
  		int tmp2=q.top();
  		q.pop();
  		Q.push(tmp2);
  		q.push(tmp);
  	}
  }
  printf("%d\n",Q.top());
  for(int i=4;i<=n;i+=2){
  	if(i==n){
  		return 0;
  	}
  	if(a[i]>a[i+1]){
  		Q.push(a[i+1]);
  		q.push(a[i]);
  	}
  	else{
  		Q.push(a[i]);
  		q.push(a[i+1]);
  	}
  	while(Q.top()>q.top()){
  		int tmp=Q.top();
  		Q.pop();
  		int tmp2=q.top();
  		q.pop();
  		Q.push(tmp2);
  		q.push(tmp);
  	}
  	printf("%d\n",Q.top());
  }
  return 0;
}