#include #include #include // Although map is not used, it's a potential alternative if MAX_VAL was very large or unknown // Define the maximum possible value for elements in A and the value x according to the problem statement. const int MAX_VAL = 100000; int main() { // Use fast I/O operations to speed up input reading. std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int N; // Number of elements in the sequence A std::cin >> N; // Create a frequency array (using std::vector) to store counts of each number from 0 to MAX_VAL. // Initialize all counts to 0. The size needs to be MAX_VAL + 1 to cover the index MAX_VAL. std::vector counts(MAX_VAL + 1, 0); // Read the initial sequence A and update the frequency counts. for (int i = 0; i < N; ++i) { int A_i; // Current element of A std::cin >> A_i; // We only need to consider values within the valid range [0, MAX_VAL] as specified. // Values outside this range might exist initially (problem states 0 <= A_i <= 10^5) // or be created, but they don't directly affect the MEX value calculation for MEX <= MAX_VAL + 1. // More importantly, any element can be changed to a value x where 0 <= x <= 10^5. // The game dynamics hinge on counts of values within [0, MAX_VAL]. if (A_i >= 0 && A_i <= MAX_VAL) { // Increment the count for the value A_i. // Optimization: Since the condition only depends on whether the count is < 2 or >= 2, // we can cap the count at 2. This prevents potentially large counts if N is large // and many elements have the same value, although it doesn't change correctness. if (counts[A_i] < 2) { counts[A_i]++; } // The simpler version `counts[A_i]++;` would also work correctly. } } // Find the smallest non-negative integer 'mex' such that its initial count is less than 2. // The logic derived is that Sente can guarantee the final MEX is at least X if and only if // for all k from 0 to X-1, the initial count of k is at least 2. // Therefore, the final MEX under optimal play will be the smallest non-negative integer X // for which the initial count is less than 2. int mex = 0; // Check values 0, 1, 2, ..., up to MAX_VAL. while (mex <= MAX_VAL) { // Check if the count of the current integer 'mex' is less than 2 (i.e., 0 or 1). if (counts[mex] < 2) { // If the count is less than 2, this is the smallest integer for which Sente cannot // guarantee its presence with count >= 2 (based on the 1-vs-1 game logic). // This 'mex' value is the final MEX of the game. break; } // If the count is 2 or more, Sente can guarantee its presence against Gote's attacks. // We continue to check the next integer. mex++; } // If the loop completes without finding any integer up to MAX_VAL with count < 2, // it means all integers from 0 to MAX_VAL have initial counts >= 2. // In this case, the smallest integer not satisfying the condition is MAX_VAL + 1. // The loop correctly results in `mex = MAX_VAL + 1` in this scenario. std::cout << mex << std::endl; // Output the determined final MEX value. return 0; // Indicate successful execution. }