#include <iostream>
 
using namespace std;
 
//returns the index i such that array[i] = i; 
//if no such element exists, return -1
int getMagicIndex(int array[], int low, int high)
{
	if( low > high )
		return -1;
 
	int mid = low + (high-low)/2;
	cout << "check" << endl;
 
	if ( array[mid] == mid )
		return mid;
	if( mid > array[mid] )
		return getMagicIndex(array, mid+1, high);
	else
		return getMagicIndex(array, low, mid-1);
}
 
int main()
{
	int array[] = {-20, -10, 0, 5, 10, 15, 20, 25, 30, 35, 40};
	int magicInd = getMagicIndex(array, 0, 11);
	cout << magicInd << endl;
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vcmV0dXJucyB0aGUgaW5kZXggaSBzdWNoIHRoYXQgYXJyYXlbaV0gPSBpOyAKLy9pZiBubyBzdWNoIGVsZW1lbnQgZXhpc3RzLCByZXR1cm4gLTEKaW50IGdldE1hZ2ljSW5kZXgoaW50IGFycmF5W10sIGludCBsb3csIGludCBoaWdoKQp7CglpZiggbG93ID4gaGlnaCApCgkJcmV0dXJuIC0xOwoKCWludCBtaWQgPSBsb3cgKyAoaGlnaC1sb3cpLzI7Cgljb3V0IDw8ICJjaGVjayIgPDwgZW5kbDsKCQoJaWYgKCBhcnJheVttaWRdID09IG1pZCApCgkJcmV0dXJuIG1pZDsKCWlmKCBtaWQgPiBhcnJheVttaWRdICkKCQlyZXR1cm4gZ2V0TWFnaWNJbmRleChhcnJheSwgbWlkKzEsIGhpZ2gpOwoJZWxzZQoJCXJldHVybiBnZXRNYWdpY0luZGV4KGFycmF5LCBsb3csIG1pZC0xKTsKfQoKaW50IG1haW4oKQp7CglpbnQgYXJyYXlbXSA9IHstMjAsIC0xMCwgMCwgNSwgMTAsIDE1LCAyMCwgMjUsIDMwLCAzNSwgNDB9OwoJaW50IG1hZ2ljSW5kID0gZ2V0TWFnaWNJbmRleChhcnJheSwgMCwgMTEpOwoJY291dCA8PCBtYWdpY0luZCA8PCBlbmRsOwoJcmV0dXJuIDA7Cn0=