§ Data structure to maintain mex

§ offline

§ online

set<int> unseen;
map<int, int> freq;
// unseen as a data structure maintains
// information about [0..largest_ever_seen]
int largest_ever_seen; 


void init() {
    unseen.insert(0);
}

void mex_insert(int k) {
    freq[k]++;
    for(int i = largest_ever_seen+1; i <= k; ++i) {
        unseen.insert(i);
    }
    unseen.erase(k);
    largest_ever_seen = max(largest_ever_seen, k);
}

void mex_delete(int k) {
    assert(freq[k] >= 1);
    freq[k]--;
    if (freq[k] == 0) {
        unseen.insert(k);
    }
}

int mex_mex() {
    assert(!unseen.empty());
    return *unseen.begin();
}