#include <iostream>
using namespace std;
int getCount(const int *a, int len, int start, int end)
{
  if (a == NULL || len <= 0)
  {
    return 0;
  }
  int count = 0;
  for (int i = 0; i < len; ++i)
  {
    if (a[i] >= start && a[i] <= end)
    {
      ++count;
    }
  }
  return count;
}
int getResetNumber(const int *a, int len)
{
  if (a == NULL || len <= 0)
  {
    return -1;
  }
  int start = 1, end = len - 1;
  //int mid = (end - start) / 2 + start;
  while (end >= start)
  {
    int mid = (end - start) / 2 + start;
    int count = getCount(a, len, start, mid);
    if (end == start)
    {
      if (count > 1)
      {
        return start;
      }
      else
      {
        break;
      }
    }
    if (count > (mid - start + 1))
    {
      end = mid;
    }
    else
    {
      start = mid + 1;
    }
  }
  return -1;
}
int main()
{
  std::cout << "請輸入數(shù)組的長度" << std::endl;
  int len = 0;
  std::cin >> len;
  if (len <= 0)
  {
    std::cout << "數(shù)組的長度不合法" << std::endl;
    return -1;
  }
  int *a = new int[len];
  std::cout << "請分別輸入數(shù)組的每個數(shù)據(jù)" << std::endl;
  for (int i = 0; i < len; ++i)
  {
    std::cin >> a[i];
    if (a[i] <= 0 || a[i] >= len)
    {
      std::cout << "輸入的數(shù)據(jù)有誤" << std::endl;
      return -1;
    }
  }
  //int count = getCount(a, len, 1, len - 1);
  int value = getResetNumber(a, len);
  if (value == -1)
  {
    std::cout << "沒有找到重復的數(shù)據(jù)" << std::endl;
    return -1;
  }
  std::cout << "其中一個重復的數(shù)據(jù)是" << value << std::endl;
  delete []a;
  return 0;
}