Problem A

#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
template<class T>
void printff(vector<T>& v) {
  for (auto k : v) cout << k << " ";
  cout << endl;
}
void SOLVE() {
  int n; cin >> n;
  vector<int> a(n), freq(n + 3);
  for(auto & val : a) cin >> val, freq[val]++;

  int mex = 0;
  for(int i = 0; i <= n + 2; i++){
    if(!freq[i]){
      mex = i;
      break;
    }
  }

  if(mex == 0){
    for(int i = n + 2; i >= 0; i--){
      if(freq[i] >= 2){
        freq[0]++;
        freq[i]--;
        break;
      }
    }
    if(!freq[0]){
      for(int i = n + 2; i >= 0; i--){
        if(freq[i]){
          freq[0]++;
          freq[i]--;
          break;
        }
      }
    }
    int answer = 0;
    for(int i = 0; i <= n + 2; i ++){
      if(!freq[i]) return void(cout << i << endl);
    }
  }else{
    for(int i = 0; i < mex; i++){
      if(freq[i] < 2) return void(cout << mex << endl);
    }
    vector<pair<int, int>> segs;

    vector<int> f(mex + 1);
    int l = 0, r = 0;
    int counter = 0;
    if(a[l] < mex) f[a[l]]++, counter++;
    while(r < n){
      r++;
      if(r < n && a[r] < mex){
        f[a[r]]++;
        if(f[a[r]] == freq[a[r]]){
          while(f[a[r]] == freq[a[r]]){
            if(a[l] >= mex){
              l++;
              continue;
            }
            f[a[l]]--;
            if(f[a[l]] == 0) counter--;
            l++;
          }
        }else if(f[a[r]] == 1){
          counter++;
        }
      }

      while(counter == mex){
        while(l < n && a[l] >= mex){
          l++;
        }
        segs.push_back({l, r});

        f[a[l]]--;
        if(f[a[l]] == 0) counter--;
        l++;
      } 
    }

    auto solve =[&](int l, int r){
      vector<int> ff(n + 2);
      for(int i = l; i <= r; i++){
        ff[a[i]]++;
      }
      int m;
      for(int i = 0; i <= n + 1; i++){
        if(!ff[i]){
          m = i;
          break;
        }
      }
      if(m != mex) return mex;
      vector<int> temp = a;
      for(int i = l; i <= r; i++){
        temp[i] = m;
      }
      for(int i = 0; i < n; i++){
        ff[temp[i]]++;
      }
      for(int i = 0; i <= n + 1; i++){
        if(!ff[i]) return i;
      }
    };

    int mx = mex;
    for(int i = 0; i < segs.size(); i++){
      mx = max(mx, solve(segs[i].first, segs[i].second));
    }
    cout << mx << endl;
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);
  int tc = 1; //cin >> tc;
  while(tc--) SOLVE();
  return 0;
}