#include <vector>

using namespace std;

/**
			1. Искать элемент за O(logn) с предподсчётом за O(nlogn)
			   Искать элемент за O(1) с предподсчётом за O(n)
			   Единственное преимущества бинпоиска: нет лишней доп памяти

			2. 	lower_bound(x) = min i : a[i] >= x
				upper_bound(x) = min i : a[i] > x
				C++:
				int i = lower_bound(a.begin(), a.end(), x) - a.begin() // a.end()
				int i = lower_bound(a, a + n, x) - a // a + n
			
			3 	f3(x) = max i : a[i] <= x : f3(x) = upper_bound(x) - 1
				f4(x) = max i : a[i] < x  : f4(x) = lower_bound(x) - 1
				Если у нас именно целые числа: upper_bound(x) = lower_bound(x+1)
*/
				
			int LowerBound( vector<int> &a, int x ) {
				int l = 0, r = a.size(); // -1
				while (l != r) {
					int m = (l + r) / 2; // a.size() <= 1'000'000'000
					if (a[m] < x)
						l = m + 1;
					else
						r = m;
				}
				return l;
			}
			
			// f : 0 0 0 0 0 1 1 1 1 1 1
			//     < < < < < >= >= (lower_bound)
			// [l, r]
			bool f( int i ) { return a[i] >= x; } // lower_bound(x)
			typedef __decltype(f) func;
			int PredicateSearch( int l, int r, func f ) {
				l--, r++; // f(l) точно 0, f(r) точно 1
				while (r - l > 1) {
					int m = (l + r) / 2; // округлять в любую сторону
					if (f(m) == 0)
						l = m;
					else
						r = m;
				}
				return l; // f(l)=0, f(r=l+1)=1
			}