Introduction
Often in O.A(Online Assessments), we see questions on Mex being asked. Therefore it's important to master such a topic. Mex of any given multiset of numbers is the smallest integer(nonnegative) that is not present in the set. Now for strengthening your concepts around Mex, we are here with an interesting problem, i.e., Mex Puzzle.
Understanding the Problem
We have been given an array 'ARR' of length 'N,' and there are 'Q' queries that we have to answer. Queries are of two kinds.
 In the first one, you will be given two integers, ' L' and 'R.' Our task is to find the Mex of the subarray formed by the occurrences of the numbers present in the subarray of 'ARR' from the Lth element to the Rth element(Inclusive).

In the second one, you will be given two integers, i.e., p and x. Our task is to simply change the element at pth index to x.
Let's understand this by the following example.
Example
Input
ARR = [1, 2, 3, 1, 1, 2, 2, 2, 9, 9]
Queries
1 1 1
1 2 8
2 7 1
1 2 8
Output
2
3
3
Explanation
 In the first query, values of ‘L’ and ‘R’ are 1 and 1, respectively; thus, the subarray formed is [1]. Now 1 has 1 frequency, so the frequency array is [1]. In this array, the smallest number that is not present in the array is 2. Thus we will print 2.
 In the second query, values of ‘L’ and ‘R’ are 2 and 8, respectively. Thus the subarray formed is [2, 3, 1, 1, 2, 2, 2, 9]. Now frequency array will be [1, 1, 2, 4]. In this array, the smallest number that is not present in the array is 3. Thus we will print 3.
 The third query is of the second type. Thus, we will simply change ARR[7]=1.
 In the third query, values of ‘L’ and ‘R’ are 2 and 8, respectively; thus, the subarray formed is [2, 3, 1, 1, 1, 2, 2, 9]. Now frequency array will be [1, 1, 3, 3]. In this array, the smallest number that is not present in the array is 2. Thus we will print 2.
Check out Euclid GCD Algorithm