// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include <vector>
#include <algorithm>
using namespace std;

void mergeSort(vector<int>, int, int);
void merge(vector<int>, int, int, int);
int check(vector<int>);

int solution(vector<int> &A) {
  // write your code in C++14 (g++ 6.2.0)
  unsigned long size = A.size();
  mergeSort(A,0, size);
  int smallest = check(A);
  return smallest;
}

int check(vector<int> A) {
  vector<int>::iterator it;
  auto start = A.begin();
  auto end = A.end();
  for(int i=1 ; i<=100000 ; i++) {
    it = find(start,end, i);
    if(it==end) {
      return i;
    }
  }
  return 100001;
}
void mergeSort(vector<int> A, unsigned long left, unsigned long right) {
  if(left < right) {
    unsigned long mid = left + (right - left)/2;
    mergeSort(A, left, mid);
    mergeSort(A, mid+1, right);

    merge(A, left, mid, right);
  }
}
void merge(vector<int> A, unsigned long left, unsigned long mid, unsigned long right) {
  unsigned long i, j, k;
  unsigned long n1 = mid - left + 1;
  unsigned long n2 = right - mid;

  vector<int> L(n1);
  vector<int> R(n2);

  for(i = 0 ; i < n1 ; i++) {
    L[i] = A[left+1];
  }
  for(j = 0 ; j < n2 ; j++) {
    R[j] = A[mid + 1 + j];
  }

  i=0;
  j=0;
  k=left;

  while (i<n1 && j<n2) {
    if(L[i]<=R[j]) {
      A[k]=R[j];
      i++;
    }
    else {
      A[k] = R[j];
      j++;
    }
    k++;
  }

  while(i < n1) {
    A[k] = L[i];
    i++;
    k++;
  }

  while(j < n2) {
    A[k] = R[j];
    j++;
    k++;
  }


}