#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
int L[1000005],R[1000005],prime[100005],arr[1000005],parent[1000005];
int n;
unordered_map <int,int> mp;
unordered_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;
}

answer.code: In function ‘void solve(int, int, int)’:
answer.code:109:13: error: no matching function for call to ‘swap(std::set<int>&, std::unordered_set<int>&)’
  109 |         swap(st2,st);
      |         ~~~~^~~~~~~~
In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:77,
                 from answer.code:1:
/usr/include/c++/13/any:429:15: note: candidate: ‘void std::swap(any&, any&)’ (near match)
  429 |   inline void swap(any& __x, any& __y) noexcept { __x.swap(__y); }
      |               ^~~~
/usr/include/c++/13/any:429:15: note:   conversion of argument 2 would be ill-formed:
answer.code:109:18: error: cannot bind non-const lvalue reference of type ‘std::any&’ to an rvalue of type ‘std::any’
  109 |         swap(st2,st);
      |                  ^~
/usr/include/c++/13/any:190:7: note:   after user-defined conversion: ‘std::any::any(_Tp&&) [with _Tp = std::unordered_set<int>&; _VTp = std::unordered_set<int>; _Mgr = _Manager_external<std::unordered_set<int> >; typename std::enable_if<(is_copy_constructible_v<_VTp> && (! __is_in_place_type_v<_VTp>)), bool>::type <anonymous> = true]’
  190 |       any(_Tp&& __value)
      |       ^~~
In file included from /usr/include/c++/13/stop_token:37,
                 from /usr/include/c++/13/condition_variable:49,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:174:
/usr/include/c++/13/bits/std_thread.h:319:3: note: candidate: ‘void std::swap(thread&, thread&)’
  319 |   swap(thread& __x, thread& __y) noexcept
      |   ^~~~
/usr/include/c++/13/bits/std_thread.h:319:16: note:   no known conversion for argument 1 from ‘std::set<int>’ to ‘std::thread&’
  319 |   swap(thread& __x, thread& __y) noexcept
      |        ~~~~~~~~^~~
In file included from /usr/include/c++/13/exception:164,
                 from /usr/include/c++/13/stdexcept:38,
                 from /usr/include/c++/13/system_error:43,
                 from /usr/include/c++/13/bits/ios_base.h:46,
                 from /usr/include/c++/13/streambuf:43,
                 from /usr/include/c++/13/bits/streambuf_iterator.h:35,
                 from /usr/include/c++/13/iterator:66,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:54:
/usr/include/c++/13/bits/exception_ptr.h:230:5: note: candidate: ‘void std::__exception_ptr::swap(exception_ptr&, exception_ptr&)’
  230 |     swap(exception_ptr& __lhs, exception_ptr& __rhs)
      |     ^~~~
/usr/include/c++/13/bits/exception_ptr.h:230:25: note:   no known conversion for argument 1 from ‘std::set<int>’ to ‘std::__exception_ptr::exception_ptr&’
  230 |     swap(exception_ptr& __lhs, exception_ptr& __rhs)
      |          ~~~~~~~~~~~~~~~^~~~~
In file included from /usr/include/c++/13/complex:45,
                 from /usr/include/c++/13/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:127:
/usr/include/c++/13/sstream:1204:5: note: candidate: ‘template<class _CharT, class _Traits, class _Allocator> void std::__cxx11::swap(basic_stringbuf<_CharT, _Traits, _Alloc>&, basic_stringbuf<_CharT, _Traits, _Alloc>&)’
 1204 |     swap(basic_stringbuf<_CharT, _Traits, _Allocator>& __x,
      |     ^~~~
/usr/include/c++/13/sstream:1204:5: note:   template argument deduction/substitution failed:
answer.code:109:13: note:   ‘std::set<int>’ is not derived from ‘std::__cxx11::basic_stringbuf<_CharT, _Traits, _Alloc>’
  109 |         swap(st2,st);
      |         ~~~~^~~~~~~~
/usr/include/c++/13/sstream:1212:5: note: candidate: ‘template<class _CharT, class _Traits, class _Allocator> void std::__cxx11::swap(basic_istringstream<_CharT, _Traits, _Allocator>&, basic_istringstream<_CharT, _Traits, _Allocator>&)’
 1212 |     swap(basic_istringstream<_CharT, _Traits, _Allocator>& __x,
      |     ^~~~
/usr/include/c++/13/sstream:1212:5: note:   template argument deduction/substitution failed:
answer.code:109:13: note:   ‘std::set<int>’ is not derived from ‘std::__cxx11::basic_istringstream<_CharT, _Traits, _Allocator>’
  109 |         swap(st2,st);
      |         ~~~~^~~~~~~~
/usr/include/c++/13/sstream:1219:5: note: candidate: ‘template<class _CharT, class _Traits, class _Allocator> void std::__cxx11::swap(basic_ostringstream<_CharT, _Traits, _Allocator>&, basic_ostringstream<_CharT, _Traits, _Allocator>&)’
 1219 |     swap(basic_ostringstream<_CharT, _Traits, _Allocator>& __x,
      |     ^~~~
/usr/include/c++/13/sstream:1219:5: note:   template argument deduction/substitution failed:
answer.code:109:13: note:   ‘std::set<int>’ is not derived from ‘std::__cxx11::basic_ostringstream<_CharT, _Traits, _Allocator>’
  109 |         swap(st2,st);
      |         ~~~~^~~~~~~~
/usr/include/c++/13/sstream:1226:5: note: candidate: ‘template<class _CharT, class _Traits, class _Allocator> void std::__cxx11::swap(basic_stringstream<_CharT, _Traits, _Allocator>&, basic_stringstream<_CharT, _Traits, _Allocator>&)’
 1226 |     swap(basic_stringstream<_CharT, _Traits, _Allocator>& __x,
      |   ...