#include <iostream>
#include <vector>
using namespace std;
struct less_than_k {
	int k;
	less_than_k(int x) : k(x) {}
	bool operator() (int m,vector<int> &v) { return v[m]<k;}
	// this assumes that the above condition is true for the first part of the range [l,r)
	// and it is false for the remaining part the search will return the first element 
	// in the search space which gives false for above condition
 
	// Hence, above condition maps as the follow over the search space
	// t t t t t t t t t t t t t t t t f f f f f f f f f f 
	// function will find the index of ^ element
};
struct less_than_equal_k {
	int k;
	less_than_equal_k(int x) : k(x) {}
	bool operator() (int m,vector<int> &v) { return v[m]<=k;}
};
template <class T, class Comp>
int binarySearch(int l, int r, Comp comp, T& t){
	int m = l+(r-l)/2;
	while(l<r){
		if(comp(m,t))	l = m+1;
		else	r = m;
		m = l+(r-l)/2;
	}
	return m;
}
int binarySearch(vector<int> &a, int k, bool strict = false){
	if(strict)	return binarySearch(0,a.size(),less_than_equal_k(k),a);
	return binarySearch(0,a.size(),less_than_k(k),a);
}
int main() {
	vector<int> a = {1,1,3,3,3,3,4,4,4,5,5};
	cout<<"4th index is less than 2: "<<less_than_k(2)(4,a)<<endl;
	cout<<"6th index is less than equal 4: "<<less_than_equal_k(4)(6,a)<<endl;
 
	cout<<"Size of array is "<<binarySearch(a,6)<<endl;
	cout<<"Count of 3 in array is "<<binarySearch(a,3,true)-binarySearch(a,3)<<endl;
	cout<<"Index of first 4 is "<<binarySearch(a,4,false)<<endl;
	cout<<"Index of last 4 is "<<binarySearch(a,4,true)-1<<endl;
	cout<<"Count of 2 in array is "<<binarySearch(a,2,true)-binarySearch(a,2)<<endl;
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwpzdHJ1Y3QgbGVzc190aGFuX2sgewoJaW50IGs7CglsZXNzX3RoYW5fayhpbnQgeCkgOiBrKHgpIHt9Cglib29sIG9wZXJhdG9yKCkgKGludCBtLHZlY3RvcjxpbnQ+ICZ2KSB7IHJldHVybiB2W21dPGs7fQoJLy8gdGhpcyBhc3N1bWVzIHRoYXQgdGhlIGFib3ZlIGNvbmRpdGlvbiBpcyB0cnVlIGZvciB0aGUgZmlyc3QgcGFydCBvZiB0aGUgcmFuZ2UgW2wscikKCS8vIGFuZCBpdCBpcyBmYWxzZSBmb3IgdGhlIHJlbWFpbmluZyBwYXJ0IHRoZSBzZWFyY2ggd2lsbCByZXR1cm4gdGhlIGZpcnN0IGVsZW1lbnQgCgkvLyBpbiB0aGUgc2VhcmNoIHNwYWNlIHdoaWNoIGdpdmVzIGZhbHNlIGZvciBhYm92ZSBjb25kaXRpb24KCQoJLy8gSGVuY2UsIGFib3ZlIGNvbmRpdGlvbiBtYXBzIGFzIHRoZSBmb2xsb3cgb3ZlciB0aGUgc2VhcmNoIHNwYWNlCgkvLyB0IHQgdCB0IHQgdCB0IHQgdCB0IHQgdCB0IHQgdCB0IGYgZiBmIGYgZiBmIGYgZiBmIGYgCgkvLyBmdW5jdGlvbiB3aWxsIGZpbmQgdGhlIGluZGV4IG9mIF4gZWxlbWVudAp9OwpzdHJ1Y3QgbGVzc190aGFuX2VxdWFsX2sgewoJaW50IGs7CglsZXNzX3RoYW5fZXF1YWxfayhpbnQgeCkgOiBrKHgpIHt9Cglib29sIG9wZXJhdG9yKCkgKGludCBtLHZlY3RvcjxpbnQ+ICZ2KSB7IHJldHVybiB2W21dPD1rO30KfTsKdGVtcGxhdGUgPGNsYXNzIFQsIGNsYXNzIENvbXA+CmludCBiaW5hcnlTZWFyY2goaW50IGwsIGludCByLCBDb21wIGNvbXAsIFQmIHQpewoJaW50IG0gPSBsKyhyLWwpLzI7Cgl3aGlsZShsPHIpewoJCWlmKGNvbXAobSx0KSkJbCA9IG0rMTsKCQllbHNlCXIgPSBtOwoJCW0gPSBsKyhyLWwpLzI7Cgl9CglyZXR1cm4gbTsKfQppbnQgYmluYXJ5U2VhcmNoKHZlY3RvcjxpbnQ+ICZhLCBpbnQgaywgYm9vbCBzdHJpY3QgPSBmYWxzZSl7CglpZihzdHJpY3QpCXJldHVybiBiaW5hcnlTZWFyY2goMCxhLnNpemUoKSxsZXNzX3RoYW5fZXF1YWxfayhrKSxhKTsKCXJldHVybiBiaW5hcnlTZWFyY2goMCxhLnNpemUoKSxsZXNzX3RoYW5fayhrKSxhKTsKfQppbnQgbWFpbigpIHsKCXZlY3RvcjxpbnQ+IGEgPSB7MSwxLDMsMywzLDMsNCw0LDQsNSw1fTsKCWNvdXQ8PCI0dGggaW5kZXggaXMgbGVzcyB0aGFuIDI6ICI8PGxlc3NfdGhhbl9rKDIpKDQsYSk8PGVuZGw7Cgljb3V0PDwiNnRoIGluZGV4IGlzIGxlc3MgdGhhbiBlcXVhbCA0OiAiPDxsZXNzX3RoYW5fZXF1YWxfayg0KSg2LGEpPDxlbmRsOwoJCgljb3V0PDwiU2l6ZSBvZiBhcnJheSBpcyAiPDxiaW5hcnlTZWFyY2goYSw2KTw8ZW5kbDsKCWNvdXQ8PCJDb3VudCBvZiAzIGluIGFycmF5IGlzICI8PGJpbmFyeVNlYXJjaChhLDMsdHJ1ZSktYmluYXJ5U2VhcmNoKGEsMyk8PGVuZGw7Cgljb3V0PDwiSW5kZXggb2YgZmlyc3QgNCBpcyAiPDxiaW5hcnlTZWFyY2goYSw0LGZhbHNlKTw8ZW5kbDsKCWNvdXQ8PCJJbmRleCBvZiBsYXN0IDQgaXMgIjw8YmluYXJ5U2VhcmNoKGEsNCx0cnVlKS0xPDxlbmRsOwoJY291dDw8IkNvdW50IG9mIDIgaW4gYXJyYXkgaXMgIjw8YmluYXJ5U2VhcmNoKGEsMix0cnVlKS1iaW5hcnlTZWFyY2goYSwyKTw8ZW5kbDsKCXJldHVybiAwOwp9