/**
  * @brief Search for Magic Index hence an array index where 
  * a[i]==i 
  */

#include <iostream>
#include <array>
#include <assert.h>
using namespace std; 

array<int, 11> data = {-40, -20, -1, 1,2,3,5,7,9,12,15}; 

template <typename T>
class MaybeResult
{
  public: 
  MaybeResult(const T& _val) : is_valid(true), val(_val) {}
  MaybeResult() : is_valid(false), val() {}

  const bool is_valid; 
  const T val; 
}; 



template <typename T>
MaybeResult<unsigned int> find_magic_index(const T& arr, const unsigned int l, const unsigned int r)
{
  if(r<l) return MaybeResult<unsigned int>(); 
  if(l==r) return  (arr[r]==r)?MaybeResult<unsigned int>(r):MaybeResult<unsigned int>(); 
  const unsigned int p = (l+r)/2; 
  if(arr[p]==p) return MaybeResult<unsigned int>(p); 
  if(arr[p] > p) return find_magic_index(arr, l, p); 
  if(arr[p] < p) return (p>l)?find_magic_index(arr, p, r):find_magic_index(arr, r, r); 
  return MaybeResult<unsigned int>(); 
}


int main() {
  std::cout << "Hello World!\n";
  assert(find_magic_index(array<int, 11>{-40, -20, -1, 1,2,3,5,7,9,12,15}, 0, data.size()-1).val == 7 ); 

  assert(find_magic_index(array<int, 11>{-40, -20, -1, 1,2,3,5,6,9,12,15}, 0, data.size()-1).is_valid == false ); 

  auto res = find_magic_index(array<int, 11>{-40, -20, -1, 1,2,3,5,7,9,12,15}, 0, data.size()-1); 
  cout << (res.is_valid?to_string(res.val):"Not Found") << endl; 
}