1619E - MEX and Increments - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second 
#define N 300005
const int mod = 998244353;
template<typename T>void print(vector<T>&a,int c=0) {
    for(auto&it :a)cout << it+c<< " ";
    cout << endl;
}
void fast() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

ll prime[N];
void sieve() {
    memset(prime,0,sizeof(prime));
    for(ll i=2;i<N;i++) {
        if(!prime[i]) {
            prime[i] = i;
            for(ll j = i*i;j<N;j+=i) {
                prime[j] = i;
            }
        }
    }
}
bool isPrime(int a) {
    if(a <= 1) return false;
    if(a <= 3) return true ;
    if(a%2 == 0 || a%3 == 0) return false;
    
    for(int i=5;i*i<=a;i+=6) {
        if(a%i == 0 || a%(i+2) == 0) return false;
    }
    return true ;
}

ll pow(ll a, ll b, ll m = 998244353) {
    if(b == 0) return 1;
    ll ans = pow(a, b / 2, m);
    
    if(b&1) return (ans * ans * a) % m;
    else return (ans * ans) % m;
}

int main(){
    fast();
    
    /* Code starts here -------------------------------------------> */
    int t;cin>>t;
    while(t--) {
        int n;cin>>n;
        vector<int>a(n);
        vector<ll>cnt(n + 1, 0), res(n + 1, -1);
        for(auto&it : a) {
            cin>>it ;
            cnt[it]++;
        }
        ll ans = 0;
        int op = 0;
        vector<pair<int ,int>>tmp;
        for(int i=0;i<=n;i++) {
            if(op != i) break;
            res[i] = 1LL * (ans + cnt[i]);
            if(cnt[i] == 0) {
                if(tmp.size() != 0) {
                    ans += 1LL * (i - tmp.back().ff);
                    ++op;
                    if(--tmp.back().ss == 0) {
                        tmp.pop_back();
                    }
                }
            }else {
                ++op;
                if(cnt[i] > 1) tmp.push_back({i, cnt[i] - 1});
            }
        }
        print(res);
    }
    
    
    
    
    
    return 0;
}