Problems on MEX

MEX is the minimum excluded value of a set of integers. For example, MEX({0,1,2,3}) = 4, MEX({1,2,3}) = 0, MEX({0,1,3}) = 2. De fine MEX(A) as the smallest non-negative integer that is not in the set A.

Here are some important properties of MEX:

1. MEX(A) can only be up to |A|, where |A| is the size of the set A. Why? Because if A contains all integers from 0 to |A|-1, then MEX(A) = |A|. If any integer in this range is missing, then MEX(A) will be less than |A|. Problems: Leetcode 2598

Consider the problem. Given a multiset S. Now you need to process Q queries. Each query is one of the following types:

1. + x: Add the integer x to the multiset S.
2. - x: Remove one occurrence of the integer x from the multiset S. It is guaranteed that x exists in S when this query is given.
3. ?: Output the MEX of the multiset S. We want to do each of these operations in O(log n) time.