#include <bits/stdc++.h>

using namespace std;

int countNumbers(const vector<int>& numbers, const int minNumber, const int maxNumber) {
  int count = 0;

  for(int i = 0; i < numbers.size(); i++) {
    if(numbers[i] >= minNumber && numbers[i] <= maxNumber) {
      count++;
    }
  }

  return count;
}

int repeatedNumberRec(const vector<int>& numbers, int minNumber, int maxNumber) {
  if(minNumber == maxNumber) {
    return minNumber;
  }

  int mid = minNumber + (maxNumber - minNumber)/2;

  int count = countNumbers(numbers, minNumber, mid);

  if(count > mid){
    return repeatedNumberRec(numbers, minNumber, mid);
  }

  return repeatedNumberRec(numbers, mid + 1, maxNumber);
}


int repeatedNumber(const vector<int>& numbers) {
  return repeatedNumberRec(numbers, 1, numbers.size() - 1);
}

int main() {
  vector<int> arr2{3,5,4,2,7,6,5,8,1};

  printf("%d\n", repeatedNumber(arr2));

  return 0;
}