#pragma once
#include<vector>usingnamespacestd;template<typenameT,typenameC>intfast_bs(constvector<T>&v,constT&x,constC&comp){if(v.empty()orcomp(x,v[0]))return0;constT*p=v.data();ints=v.size();intt=63-__builtin_clzll(s);intb=s-(1<<t);intl=comp(x,p[b])?0:b;if(t==0)returnl+1;for(intd=1<<(t-1);d;d/=2){l=comp(x,p[l+d])?l:l+d;}returnl+1;}template<typenameT>intfast_lb(constvector<T>&v,constT&x){returnfast_bs(v,x,std::less_equal<T>{});}template<typenameT>intfast_ub(constvector<T>&v,constT&x){returnfast_bs(v,x,std::less<T>{});}