Спасибо! Поправил.

Thanks! I will.

Thanks!

Thank you for your support!

I'm gonna translate my old videos to English in the nearest future. Thanks!

Thank you

EDIT: lemelisk pointed out that we can use sqrt decomposition instead of a set.

And also you can check out the pinned comment. There's a $$$O(n \log^2 n)$$$ solution!

Mex always will be $$$\le n$$$, so instead of set we can use fenwick/segment tree built on array $$$0 \ldots n$$$ — add/remove will be point updates and lifting for find mex. This substitution already improves constant factor by a lot.

Further, let's replace this trees by sqrt decomposition built on the same array. Then lifting will become $$$O(\sqrt{n})$$$, but update will be $$$O(1)$$$. Since we make only $$$q$$$ liftings and a lot of updates, it will improve our time to $$$O(n^{5/3} + q \sqrt{n})$$$.

Oh, yeah. I should've added it to this post too.

P.S. Done.