"""Original exact prefix median via balanced two heaps; memory is linear."""
import heapq,json
from fractions import Fraction as F
from itertools import product
from collections import Counter

def run(values):
 if type(values) is not list or len(values)>16 or any(type(x) is not int or abs(x)>1000 for x in values):raise ValueError('0..16 bounded integer values, no bool')
 low=[];high=[];rows=[]
 for i,x in enumerate(values):
  moves=[]
  if not low or x<=-low[0]:heapq.heappush(low,-x);inserted='lower_max_heap_stored_negated'
  else:heapq.heappush(high,x);inserted='upper_min_heap'
  if len(low)>len(high)+1:v=-heapq.heappop(low);heapq.heappush(high,v);moves.append({'value':v,'from':'lower','to':'upper'})
  if len(high)>len(low):v=heapq.heappop(high);heapq.heappush(low,-v);moves.append({'value':v,'from':'upper','to':'lower'})
  assert len(low) in [len(high),len(high)+1] and (not high or -low[0]<=high[0])
  assert Counter([-v for v in low]+high)==Counter(values[:i+1])
  median=F(-low[0]) if len(low)>len(high) else F(-low[0]+high[0],2)
  rows.append({'prefix_length':i+1,'inserted_value':x,'inserted_into':inserted,'rebalance_moves':moves,'lower_values_sorted':sorted(-v for v in low),'upper_values_sorted':sorted(high),'lower_size':len(low),'upper_size':len(high),'median':str(median)})
 return rows

def oracle(values):
 if not values:return None
 s=sorted(values);n=len(s);return F(s[n//2]) if n%2 else F(s[n//2-1]+s[n//2],2)

def demo():
 data=[5,1,9,2,2,8];rows=run(data);assert [r['median'] for r in rows]==['5','3','5','7/2','2','7/2']
 cases=0;prefixes=0
 for n in range(7):
  for chars in product([-1,0,1],repeat=n):
   vals=list(chars);trace=run(vals)
   for i,row in enumerate(trace,1):assert F(row['median'])==oracle(vals[:i]);prefixes+=1
   cases+=1
 assert cases==1093 and prefixes==6015 and oracle([]) is None and run([])==[]
 rejected=[]
 for bad in [[True],[1.5],[float('nan')],[float('inf')],[0]*17]:
  try:run(bad)
  except ValueError:rejected.append(repr(bad))
  else:raise AssertionError('expected rejection')
 return {'authored_values':data,'all_prefix_heap_states':rows,'all1093_ternary_sequences_oracle_checks':{'sequences':cases,'prefixes':prefixes},'wrong_old_median_average':{'prefix':[5,1,9],'previous_median':'3','new_value':9,'wrong_average':'6','correct_median':'5'},'empty_median':None,'retained_heap_values':len(data),'invalid_inputs_rejected':rejected,'scope':'exact append-only prefix median, two heaps retain allnvalues O(n) memory, no fixed-memory sketch/sliding deletion/realcallstats/benchmark; full teaching traces and oracle also have separate storage cost'}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))