#include <iostream>
using namespace std;
int main() {
// your code goes here
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKSB7CgkvLyB5b3VyIGNvZGUgZ29lcyBoZXJlCglyZXR1cm4gMDsKfQ==
aW50IEJpbmFyeVNlYXJjaCggdmVjdG9yJmx0O2ludCZndDsgYXJyLCBpbnQgVGFyZ2V0KQp7CiBpbnQgbGVmdCA9IDA7CiBpbnQgcmlnaHQgPSBhcnIuc2l6ZSgpIC0gMTsKIHdoaWxlKGxlZnQgJmx0Oz0gcmlnaHQpCiB7CiBpbnQgbWlkID0gKGxlZnQgKyByaWdodCkgLyAyOwogaWYoYXJyW21pZF0gPT0gVGFyZ2V0KQogewogcmV0dXJuIG1pZDsKIH0KIGVsc2UgaWYoYXJyW21pZF0gJmx0OyBUYXJnZXQpCiB7CiBsZWZ0ID0gbWlkICsgMTsKIH0KIGVsc2UKIHsKIHJpZ2h0ID0gbWlkIC0gMTsKIH0KIH0KIHJldHVybiAtMTsKfQ==
int BinarySearch( vector<int> arr, int Target)
{
int left = 0;
int right = arr.size() - 1;
while(left <= right)
{
int mid = (left + right) / 2;
if(arr[mid] == Target)
{
return mid;
}
else if(arr[mid] < Target)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return -1;
}