#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
template<int n, typename T>
int lowerBound(const T* __restrict arr, const T val) {
	if (n == 1) { return val > arr[0]; } 
	else {
		constexpr int mid = n / 2;
		if (val > arr[mid]) { return mid+lowerBound<n-mid, T>(arr+mid, val); }
		else { return lowerBound<mid, T>(arr,val); }
	}
};

template<int n, typename T>
int loserBound(const T* __restrict arr, const T val) {
    return int(std::lower_bound(arr,arr+n,val)-arr);
}

int main() {
	static double arr[1 << 20];
	for (int i = 0; i < (1 << 20); i++) { arr[i] = i; }
	std::mt19937 gen;
	std::uniform_real_distribution<double> dist(0, 1 << 20);
	std::vector<double> queries(1 << 9);
	for (auto &it : queries) { it = dist(gen); }
	#define TEST(s, f) \
	{ \
		std::cout << s << std::endl; \
		int res = 0; \
		double tin = (double)clock(), tout; \
		for (int i = 0; i < (1 << 15); i++) {\
			for (auto q : queries) { \
				res += f<1<<20>(&arr[0],q); \
			} \
		} \
		tout = (double)clock(); \
		std::cout << "time = " << (tout - tin) / CLOCKS_PER_SEC << "s, sum = " << res << std::endl; \
	}
	TEST("Testing std::lower_bound...", loserBound);
	TEST("Testing lowerBound...", lowerBound);
	return 0;
}