959D - Mahmoud and Ehab and another array construction task - CodeForces Solution

//jiudge: 23888: 1686552841
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long

using namespace std;

const int N = 2e6 + 5;

set<int> s;
int n;
int a[N], b[N];
bool f;

void del(int x) {
    for (int i = 2; i * i <= x; i ++) {
        if (x % i == 0) {
            for (int j = i; j < N; j += i) if (s.count(j)) s.erase(j);
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) for (int i = x; i < N; i += x) if (s.count(i)) s.erase(i);
}

int main() {
    IOS
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 2; i < N; i ++) s.insert(i);
    for (int i = 1; i <= n; i ++) {
        auto it = f ? s.begin() : s.lower_bound(a[i]);
        if (*it > a[i]) f = 1; b[i] = *it; del(*it);
    }
    for (int i = 1; i <= n; i ++) cout << b[i] << ' ';
    return 0;
}