作为竹林的粉丝来发的题解，发现在符合条件的情况下，即a数组满足单调不增，且后一位能整除前一位的情况下，对于a数组中发生降落的部分，必须使用对应的数字来进行填充，因为根据倍数填充可能不会导致gcd发生降落。

所以采用两部分进行构造，居然没有TLE

```#include <bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
#define pb push_back
#define ull unsigned long long
#define all(a) a.begin(), a.end()
#define vi vector<int>
#define vii vector<vector<int>>
#define fi first
#define se second
#define vs vector<string>
#define eb emplace_back
#define in insert
#define pf push_front
#define sep "================"
#define ios                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);                  \
    cout.tie(nullptr);
const int inf = 2e18 + 9;
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
typedef pair<int, int> pll;
typedef long double db;
inline void pt(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        pt(x / 10);
    putchar(x % 10 + '0');
}
inline void print(int x) { pt(x), puts(""); }
inline void print(pll x) { pt(x.fi), putchar(' '), pt(x.se), putchar('\n'); }
inline void print(vi &vec)
{
    for (const auto t : vec)
        pt(t), putchar(' ');
    puts("");
}
inline void print(vector<pll> &vec)
{
    puts(sep);
    for (const auto v : vec)
    {
        print(v);
    }
    puts(sep);
}
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; };
inline int qsm(int a, int b, int mod) ;
inline int lem(int a, int b) { return a * b / (gcd(a, b)); }
inline int lowbit(int x){return (~x + 1) & x ; }
vii mul(vii &h1, vii h2)
{
    int a1 = h1.size();
    int a2 = h2[0].size();
    int a3 = h1[0].size();
    vii ans(a1, vi(a2, 0));
    for (int i = 0; i < a1; i++)
    {
        for (int j = 0; j < a2; j++)
        {
            for (int k = 0; k < a3; k++)
            {
                ans[i][j] = (ans[i][j] + (__int128)h1[i][k] * h2[k][j]) % (mod2 - 1);
            }
        }
    }
    return ans;
}
inline int read()
{
    int x = 0;
    short f = 1;
    char c = getchar();
    while ((c < '0' || c > '9') && c != '-')
        c = getchar();
    if (c == '-')
        f = -1, c = getchar();
    while (c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    x *= f;
    return x;
}
int per(int n, int m)
{
    if (m == 0)
    {
        return 1;
    }
    int result = 1;
    for (int i = 0; i < m; ++i)
    {
        result *= (n - i);
    }
    return result;
}
void C()
{
    const int N = 200005 + 10;
    int inv[N];
    int jie[N];
    jie[0] = 1;
    for (int i = 1; i < N; i++)
    {
        jie[i] = jie[i - 1] * i % mod1;
    }
    inv[N - 1] = qsm(jie[N - 1], mod1 - 2, mod1);
    for (int i = N - 2; i >= 0; i--)
    {
        inv[i] = inv[i + 1] * (i + 1) % mod1;
    }
}
struct ss
{
    vi t ; 
    ss() {}
    ss(int n) : t(n) {}
    void add(int x , int y)
    {
        for(int i = x ; i < t.size() ; i += lowbit(i))
        {
            t[i] += y ;
        }
    }
    int ask(int x)
    {
        int sum = 0 ; 
        for(int i = x ; i ; i -= lowbit(i))
        {
            sum += t[i] ;
        }
        return sum ; 
    }
};
// inline int comb(int n, int r){if (r < 0 || r > n)return 0;return jie[n] * inv[r] % mod1 * inv[n - r] % mod1;}
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int dirx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int diry[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
void init()
{
}
void work()
{ 
    int n ; cin >> n ;
    vector<queue<int>>q(n + 1) ;
    vector<bool>vis(n + 1 , false) ;
    for(int i = n ; i >= 1 ; i--)
    {
        int g = n / i ;
        for(int j = 1 ; j <= g ; j++)
        {
            q[i].push(j * i) ;
        }
    }
    vi ne(n + 1) ;
    vi a(n + 1) ; 
    for(int i = 1 ; i <= n ; i++)cin >> a[i] ;
    for(int i = 2 ; i <= n ; i++)
    {
        if(a[i] > a[i - 1] || a[i - 1]%a[i] != 0)
        {
            cout << -1 << endl ; 
            return ; 
        }
    }
    ne[1] = a[1] ;
    vis[a[1]] = true ;
    for(int i = 2 ; i <= n ; i++)
    {
        if(a[i] < a[i - 1])
        {
            ne[i] = a[i] ; 
            vis[a[i]] = true ;
        }
    }
    for(int i = 1 ; i <= n ; i++)
    {
        if(ne[i] == 0)
        {
            while(vis[q[a[i]].front()])q[a[i]].pop() ;
            if(q[a[i]].empty())
                  {
                      cout << -1 << endl ;
                      return ;
                  }
            else
            {
                ne[i] = q[a[i]].front() ; vis[ne[i]] = true ;
                q[a[i]].pop() ; 
            }
        }
    }
    for(int i = 1 ; i <= n ; i++)cout << ne[i] << " " ; 
    cout << endl ; 
}
signed main()
{
    init();
    ios;
    int dragon = 1;
    // cin >> dragon ; 
    while (dragon--)
    {
        work();
    }
    return 0;
}
inline int qsm(int a, int b, int mod)
{
    int res = 1;
    a %= mod ; 
    while (b)
    {
        if (b & 1)
        {
            res = res * a % mod;
        }
        b >>= 1;
        a = a * a % mod;
    }
    return res % mod;
}