No bro, brute forcing to finding the mex till $$$2n$$$ elements takes $$$O(n^2)$$$ time because each computation can take $$$O(n)$$$. You need to use some data structure to speed this up to $$$O(log n)$$$ or $$$O(1)$$$ per computation.

How does your "easy" formula work, and how do you brute force efficiently (n=1e5)?

My solution is as follows: First observe that s_{i+1},...,s_{i+n} cannot be equal to s_{i}, and furthermore for i>n, we have s_{i} <= n, since it is the mex of n numbers. Hence for i>n, the sequence is periodic with period n+1, and s_{n+1},...,s_{2n+2} are a permutation of 0,...,n.

To find this permutation, we can use an std::set that stores the numbers from 0,...,n that do not occur in our 'current' window of n elements. we can find the MEX by doing *set.begin(), and update the set by adding numbers s_{i-n} to it if it is the last occurrence of s_{i-n} in the interval, and removing s_{i} from the set, since after the interval moves one place to the right it will contain s_{i}.

I am not sure if there is an easier way? what is your solution?

Of course!

aight, calm down:

#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i)
typedef long long ll;
typedef vector<int> vi;

void solve(){
    int n,q; cin >> n >> q;
    vi a(n), cnt(n+1), perm(n+1);
    for(auto& c : a) cin >> c;
    set<int> missing;
    rep(i,0,n) if (a[i]<=n) cnt[a[i]]++;
    rep(i,0,n+1) if (cnt[i]<1) missing.insert(i);
    rep(i,0,n+1){
        perm[i] = *begin(missing);
        missing.erase(perm[i]);
        cnt[perm[i]]++;
        if (i<n) {
            cnt[a[i]]--;
            if (cnt[a[i]]<1) missing.insert(a[i]);
        }
    }
    while(q--){
        ll x; cin >> x; --x;
        if (x<n) cout << a[x] << '\n';
        else cout << perm[(x-n)%(n+1)] << '\n';
    }
}

int main(){
    cin.tie(NULL),cin.sync_with_stdio(false);
    
    int t; cin >> t;
    while(t--) solve();
}

Following is my approach: Simply find the MEX of the initial array, and that will be the element at the (n)th index (0-based) , these elements keep repeating, therefore element at index k is the same as the element at index k%(n+1)

/* Coded by harshcooljn */

#include <bits/stdc++.h>
#include <iostream>
#include <stdint.h>
#include <ios>
#include <iomanip>
#include <numeric>
#include <math.h>
#include <vector>
#include <stdlib.h>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <string>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef unsigned long long int ull;
typedef pair<ll, ll> pll;
#define vll vector<ll>
#define vstr vector<string>
#define vvll vector<vector<ll> >
#define vpll vector<pair<ll,ll> >
#define endl '\n'
#define vin(v,a,n) for(ll i=a;i<n;i++){cin>>v[i];}
#define vinp(v,n) for(ll i=0;i<n;i++){ll x;cin>>x;v.push_back(x);}
#define pvec(v) for(auto &e: v){cout << e << " ";}cout<<endl;
#define pvecp(v) for (ll i=0;i<v.size();i++){cout << v[i].first << "," << v[i].second << " \n"[i==v.size()-1];}
#define parr(a,n) for(ll i=0;i<n;i++){cout << a[i] << "";}
#define parr1(a,n) for(ll i=1;i<=n;i++){cout << a[i] << "";}
#define yes cout<<"YES"<<endl;
#define full(v) v.begin(),v.end()
#define fr(i,a,n) for(ll i=a;i<n;i++)
#define fr_(i,n,a) for (ll i=n;i>=a;i--)
#define no cout<<"NO"<<endl;
#define spc ' '
#define nline cout<<endl;
#define fileIO freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)
#define fastIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)


void Solve(ll t10) {
    ll n,q;
    cin >> n >> q;
    vll a(n+1);
    set<ll> st;
    fr(i,0,n+1){
        st.insert(i);
    }
    fr(i,0,n){
        cin >> a[i];
        st.erase(a[i]);
    }
    a[n] = *st.begin(); // this is the mex of elements from [0,n-1] (0 - based index)
    while (q--){
        ll k;
        cin >> k;
        k--;
        cout << a[k%(n+1)] << " ";
    }
    cout << endl;
}

int main() {
    fastIO;
    // fileIO;
    ll t;cin >> t;fr(c, 1, t + 1) Solve(c);
    // Solve(1);
    return 0;
}

UPD : I assumed that the elements were distinct , my bad

Bro if $$$a_i \gt n$$$ it just doesn't matter since the MEX is at most $$$n$$$. If the value $$$k$$$ of the query is at most $$$n$$$ just output the value itself else take all values greater than $$$n$$$ to be $$$n$$$ and calculate the MEX normally like the solution.

Also, you will lose generality because the sequence values depend on the last $$$n$$$ terms which may not necessarily be sorted. Thus, the WLOG part is also wrong according to me.

Yes, that is right!

More specifically, I was born on 17 February 2013.