/*
¤ï¤ó¤ï¤ó¡­¡­¤ï¤ó¤À¤Û©`¤¤¤Ã¡î
Wonderhoy!
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;
char buf[1<<21],*p1=buf,*p2=buf;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++)
int read()
{
	int x=0;
	char c=getchar();
	while(c<'0' || c>'9')	c=getchar();
	while(c>='0' && c<='9')	x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
	return x;
}
void write(int x)
{
	if(x>9)	write(x/10);
	putchar(x%10+'0');
}
typedef pair<int,int> P;
typedef vector<int> Poly;
typedef vector<P> PolyP;
#define mp make_pair
#define spc putchar(' ')
#define etr putchar('\n')
#define inlp(x,y) putchar(x==y?'\n':' ')
int prime[3000005],cnt;
int mnp[10000005];
bool vis[10000005];
void shai(int up)
{
	vis[1]=true;
	for(int i=2;i<=up;++i)
	{
		if(!vis[i])	prime[++cnt]=mnp[i]=i;
		for(int j=1;j<=cnt && prime[j]*i<=up;++j)
		{
			if(!vis[prime[j]*i])	mnp[prime[j]*i]=prime[j];
			vis[prime[j]*i]=true;
			if(i%prime[j]==0)	break;
		}
	}
}
int n;
int a[1000005];
int ap[10000005];
int L[1000005],R[1000005];
int fa[1000005];
int Solve(int l,int r)
{
	if(l>r)	return 0;
	if(l==r)	return l;
	int rt=-1;
	for(int i=l,j=r;i<=j;++i,--j)
	{
		if(L[i]<l && r<R[i])
		{
			rt=i;
			break;
		}
		if(L[j]<l && r<R[j])
		{
			rt=j;
			break;
		}
	}
	if(rt==-1)	exit(puts("impossible")&0);
	fa[Solve(l,rt-1)]=fa[Solve(rt+1,r)]=rt;
	return rt;
}
int main(){
	n=read();
	for(int i=1;i<=n;++i)	a[i]=read();
	shai(*max_element(a+1,a+1+n));
	for(int i=1;i<=n;++i)
	{
		int w=a[i];
		while(w^1)	L[i]=max(L[i],ap[mnp[w]]),w/=mnp[w];
		w=a[i];
		while(w^1)	ap[mnp[w]]=i,w/=mnp[w];
	}
	for(int i=1;i<=1e7;++i)	ap[i]=n+1;
	for(int i=n;i;--i)
	{
		R[i]=n+1;
		int w=a[i];
		while(w^1)	R[i]=min(R[i],ap[mnp[w]]),w/=mnp[w];
		w=a[i];
		while(w^1)	ap[mnp[w]]=i,w/=mnp[w];
	}
	Solve(1,n);
	for(int i=1;i<=n;++i)	write(fa[i]),inlp(i,n);
	return 0;
}