Core Idea
The MEX is the smallest non-negative value whose frequency is zero. Updates only change the frequencies of the old value and the new value.
Algorithm
Maintain frequencies and a set of currently missing values. After each update, adjust the two affected values and read the smallest element of the missing set.
Common Mistakes
Only values from 0 through n are needed for MEX of an array of length n; larger values can affect frequencies but never become the answer.