"""Original lower/upper loops with bounded sorted-input contract."""
from bisect import bisect_left,bisect_right
from itertools import combinations_with_replacement
import json
def bound(a,x,right=False,trace=False):
 if type(a) is not list or len(a)>32 or any(type(v) is not int or abs(v)>1000 for v in a) or type(x) is not int or abs(x)>1000 or any(a[i]>a[i+1] for i in range(len(a)-1)):raise ValueError('bounded sorted integer sequence and integer query')
 lo=0;hi=len(a);rows=[]
 while lo<hi:
  mid=(lo+hi)//2;old=[lo,hi]
  if a[mid]<x or (right and a[mid]==x):lo=mid+1
  else:hi=mid
  assert all(v<=x if right else v<x for v in a[:lo]) and all(v>x if right else v>=x for v in a[hi:])
  if trace:rows.append({'before_halfopen':old,'mid':mid,'value':a[mid],'after_halfopen':[lo,hi]})
 return lo,rows
def demo():
 a=[-2,0,0,0,3,7];l,lt=bound(a,0,False,True);r,rt=bound(a,0,True,True);assert (l,r)==(1,4)
 queries=[];checks=0;range_checks=0
 for n in range(7):
  for p in combinations_with_replacement([0,1,2],n):
   b=list(p)
   for x in [-1,0,1,2,3]:
    ll,_=bound(b,x);rr,_=bound(b,x,True);assert ll==sum(v<x for v in b)==bisect_left(b,x) and rr==sum(v<=x for v in b)==bisect_right(b,x);checks+=1
   for low,high in combinations_with_replacement([-1,0,1,2,3],2):
    ll,_=bound(b,low);rr,_=bound(b,high,True);assert rr-ll==sum(low<=v<=high for v in b);range_checks+=1
 for x in [-3,0,1,8]:
  ll,_=bound(a,x);rr,_=bound(a,x,True);queries.append({'x':x,'left':ll,'right':rr,'count_equal':rr-ll,'membership':ll<len(a) and a[ll]==x})
 rejected=[]
 for b,x in [([2,1],1),([0,1],True),([0,False],0)]:
  try:bound(b,x)
  except ValueError:rejected.append([repr(b),repr(x)])
  else:raise AssertionError('expected rejection')
 return {'sorted_data':a,'query_zero':{'lower_bound':l,'upper_bound':r,'equal_halfopen_range':[l,r],'count':r-l},'lower_trace':lt,'upper_trace':rt,'edge_queries':queries,'sorted_array_query_checks':checks,'inclusive_value_range_count_checks':range_checks,'rejected':rejected,'complexity_scope':'binary loop logarithmic; validation and executable invariant assertions scan data and are teaching overhead; no benchmark','index_contract':'positions in already-sorted input, insertion position is not membership; no mutation or hidden sorting'}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))