#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
int dp1[20][200005], dp2[20][200005];
int loc1[20][200005], loc2[20][200005];
int arr[200005];
int n;

void setup() {
	for (int i=0; i<20; i++) {
		for (int j=0; j<200005; j++) {
			dp1[i][j]=1000000000;
			dp2[i][j]=1000000000;
		}
	}
	for (int i=0; i<n; i++) {
		if (i%2==0) {
			dp1[0][i]=arr[i];
			loc1[0][i]=i, loc2[0][i]=i;
		}
		else {
			dp2[0][i]=arr[i];
			loc1[0][i]=i, loc2[0][i]=i;
		}
	}
	for (int i=1; i<20; i++) {
		for (int j=0; j<n-(1<<(i-1)); j++) {
			//printf("%d %d\n", dp1[i-1][j], dp1[i-1][j+(1<<(i-1))]);
			dp1[i][j]=min(dp1[i-1][j],dp1[i-1][j+(1<<(i-1))]);
			dp2[i][j]=min(dp2[i-1][j],dp2[i-1][j+(1<<(i-1))]);
			
			if (dp1[i-1][j]<dp1[i-1][j+(1<<(i-1))]) {
				loc1[i][j]=loc1[i-1][j];
			}
			else loc1[i][j]=loc1[i-1][j+(1<<(i-1))];
			if (dp2[i-1][j]<dp2[i-1][j+(1<<(i-1))]) {
				loc2[i][j]=loc2[i-1][j];
			}
			else loc2[i][j]=loc2[i-1][j+(1<<(i-1))];
		}
	}
}

inline int rmq(int x, int y) {
	int lng=31-__builtin_clz(y-x+1);
	if (x%2==0) {
		if (dp1[lng][x]<dp1[lng][y+1-(1<<lng)]) return loc1[lng][x];
		else return loc1[lng][y+1-(1<<lng)];
	}
	else {
		if (dp2[lng][x]<dp2[lng][y+1-(1<<lng)]) return loc2[lng][x];
		else return loc2[lng][y+1-(1<<lng)];
	}
}

vector<deque<int> > vc;
deque<int> emp;

int fnd(int x, int y) {
	int fst=rmq(x,y);
	int scd=rmq(fst+1,y);
	//printf("%d %d %d %d\n", x, y, fst, scd);
	int bef=-1, btn=-1, aft=-1;
	if (x<fst) bef=fnd(x,fst-1);
	if (fst!=scd-1) btn=fnd(fst+1,scd-1);
	if (scd<y) aft=fnd(scd+1,y);
	if (vc.size()==0 || vc[vc.size()-1].size()!=0) vc.push_back(emp);
	int ans=vc.size()-1;
	//printf("%d %d %d\n", bef, btn, aft);
	if (bef==-1 && btn==-1 && aft==-1) {
		vc[ans].push_back(fst);
		vc[ans].push_back(scd);
		return ans;
	}
	//printf("FIN\n");
	if (bef==-1) {
		if (btn==-1) {
			vc[aft].push_front(scd);
			vc[aft].push_front(fst);
			return aft;
		}
		if (aft==-1) {
			vc[btn].push_front(scd);
			vc[btn].push_front(fst);
			return btn;
		}
	}
	else if (btn==-1 && aft==-1) {
		vc[bef].push_front(scd);
		vc[bef].push_front(fst);
		return bef;
	}
	int i1=0, i2=0, i3=0;
	int s1=bef==-1 ? 0 : vc[bef].size();
	int s2=btn==-1 ? 0 : vc[btn].size();
	int s3=aft==-1 ? 0 : vc[aft].size();
	
	//printf("%d %d %d\n", s1, s2, s3);
	while (!(i1==s1 && i2==s2 && i3==s3)) {
		int ar[3]={1000000000, 1000000000, 1000000000};
		if (i1!=s1) {
			ar[0]=arr[vc[bef][i1]];
		}
		if (i2!=s2) {
			ar[1]=arr[vc[btn][i2]];
		}
		if (i3!=s3) {
			ar[2]=arr[vc[aft][i3]];
		}
		//printf("%d %d %d %d %d %d\n", i1, i2, i3, ar[0], ar[1], ar[2]);
		//break;
		if (ar[0]<ar[1] && ar[0]<ar[2]) {
			vc[ans].push_back(vc[bef][i1]);
			vc[ans].push_back(vc[bef][i1+1]);
			i1+=2;
		}
		else if (ar[1]<ar[0] && ar[1]<ar[2]) {
			vc[ans].push_back(vc[btn][i2]);
			vc[ans].push_back(vc[btn][i2+1]);
			i2+=2;
		}
		else if (ar[2]<ar[0] && ar[2]<ar[1]) {
			vc[ans].push_back(vc[aft][i3]);
			vc[ans].push_back(vc[aft][i3+1]);
			i3+=2;
		}
	}
	vc[ans].push_front(scd);
	vc[ans].push_front(fst);
	//printf("!%d %d\n", x, y);
	return ans;
}

int main() {
	scanf("%d", &n);
	for (int i=0; i<n; i++) {
		scanf("%d", &arr[i]);
	}
	setup();
	int ptr=fnd(0,n-1);
	for (int i=0; i<n; i++) {
		printf("%d%c", arr[vc[ptr][i]], i==n-1 ? '\n':' ');
	}
}


Measured memory_bytes: 181260