#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
int L[1000005],R[1000005],prime[100005],arr[1000005],parent[1000005];
int n;
map <int,int> mp;
set <int> st;
vector <int> v[1000005];
void buildL(int i){
    int a=arr[i];
    //cout<<arr[i]<<endl;
    for(int j=1;j<=sqrt(arr[i]);j++){
        if(a%j!=0||prime[j]==1) continue;
        int div=j;
        if(L[i]==0) L[i]=mp[div];
        else L[i]=max(L[i],mp[div]);
        while(a%div==0) a/=div;
        mp[div]=i;
    }
    if(a!=1){
        int div=a;
        if(L[i]==0) L[i]=mp[div];
        else L[i]=max(L[i],mp[div]);
        while(a%div==0) a/=div;
        mp[div]=i;
    }
    return;
}
void buildR(int i){
    int a=arr[i];
    for(int j=1;j<=sqrt(arr[i]);j++){
        if(a%j!=0||prime[j]==1) continue;
        int div=j;
        if(R[i]==0) R[i]=mp[div];
        else if(mp[div]!=0) R[i]=min(R[i],mp[div]);
        while(a%div==0) a/=div;
        mp[div]=i;
    }
    if(a!=1){
        int div=a;
        if(R[i]==0) R[i]=mp[div];
        else if(mp[div]!=0) R[i]=min(R[i],mp[div]);
        while(a%div==0) a/=div;
        mp[div]=i;
    }
    if(R[i]==0) R[i]=n+1;
    //if(i==6) exit(0);
    return;
}
void build(){
    prime[1]=prime[0]=1;
    for(int i=2;i<=sqrt(10000000);i++){
        for(int j=i+i;j<=sqrt(10000000);j+=i) prime[j]=1;
    }
    //for(int i=2;i<=sqrt(10000000);i++) if(prime[i]==0) prm.push_back(i);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        buildL(i);
    }
    mp.clear();
    for(int i=n;i>=1;i--){
        buildR(i);
        //cout<<L[i]<<" "<<R[i]<<endl;
        v[L[i]].push_back(i);
        v[R[i]].push_back(i);
    }
    for(int i=1;i<=n;i++) sort(v[i].begin(),v[i].end());
    return;
}
void imp(){
    cout<<"impossible";
    exit(0);
}
int check(int i){
    if(L[i]==0&&R[i]==n+1) return 1;
    else return 0;
}
void solve(int l,int r,int pre){
    if(l>r) return;
    if(st.size()==0) imp();
    int rt=*st.begin(),siz1=rt-l,siz2=r-rt;
    set <int> st2;
    parent[rt]=pre;
    st.erase(rt);
    if(siz1<=siz2){
        for(int i=l;i<rt;i++){
            if(R[i]>=rt) R[i]=n+1;
            if(check(i)==1){
                st.erase(i);
                st2.insert(i);
            }
            int l1=0,r1=v[i].size()-1,idx=v[i].size();
            while(l1<=r1){
                int mid=(l1+r1)/2;
                if(v[i][mid]>rt){
                    idx=mid;
                    r1=mid-1;
                }
                else l1=mid+1;
            }
            for(int j=idx;j<v[i].size();j++){
                if(v[i][j]>r) break;
                L[v[i][j]]=0;
                if(check(v[i][j])==1) st.insert(v[i][j]);
            }
        }
        solve(rt+1,r,rt);
        swap(st2,st);
        solve(l,rt-1,rt);
    }
    else{
        for(int i=rt+1;i<=r;i++){
            if(L[i]<=rt) L[i]=0;
            if(check(i)==1){
                st.erase(i);
                st2.insert(i);
            }
            int l1=0,r1=v[i].size()-1,idx=-1;
            while(l1<=r1){
                int mid=(l1+r1)/2;
                if(v[i][mid]<rt){
                    idx=mid;
                    l1=mid+1;
                }
                else r1=mid-1;
            }
            for(int j=idx;j>=0;j--){
                if(v[i][j]<l) break;
                R[v[i][j]]=n+1;
                if(check(v[i][j])==1) st.insert(v[i][j]);
            }
        } 
        solve(l,rt-1,rt);  
        swap(st2,st);
        solve(rt+1,r,rt);
    }
    return;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    build();
    for(int i=1;i<=n;i++) if(check(i)==1) st.insert(i);
    solve(1,n,0);
    for(int i=1;i<=n;i++) cout<<parent[i]<<" ";
    return 0;
}