#include <iostream>
#include <vector>
#include <algorithm>

std::size_t binarySearch(const std::vector<int>::iterator begin, const std::vector<int>::iterator end, const int val) {
	std::size_t left = begin;
	std::size_t right = end;
	while (right > left) {
		std::size_t middle = begin + (end-begin)/2;
		if (*middle > val) {
			right = middle;
		} else {
			left = middle + 1;
		}
	}
	return left;
}