import sys,math,random
sys.dont_write_bytecode = True

class Sym:
  "An Accumulator for syms"
  def __init__(i): 
    i.n=i.most=0; i.mode= None; i.counts={}
  def __add__(i,x):
    i.n += 1    
    new  = i.counts.get(x,0) + 1
    if new > i.most:
      i.most, i.mode = new, x
    i.counts[x] = new

def chops(lst,n):
  "Equal frequency binning."
  out,i,j,last = [],0,0,None
  for bins in range(n,1,-1):
    if j >= len(lst) : 
      out[-1] += lst[i:]
      break
    if i: 
      out += [lst[i:j]]
      last = out[-1][-1]
    i  = j
    j += int((len(lst) - j)*1.0 /bins)
    # jump runs of similar values
    while j < len(lst) and lst[j] == last
      j += 1
  return out

class Num:
  "An Accumulator for numbers"
  def __init__(i,init=[],cache=128): 
    i.n = i.m2 = i.mu = 0.0
    i.hi, i.lo = -1*10**32, 10**32
    i.some = Sample(cache=cache)
    for x in init: i + x
  def s(i) : return (i.m2/(i.n - 1))**0.5
  def __lt__(i,j): return i.mu < j.mu
  def __add__(i,x):
    i.some + x
    if x > i.hi: i.hi = x
    if x < i.lo: i.lo = x
    i.n   += 1    
    delta  = x - i.mu
    i.mu  += delta*1.0/i.n
    i.m2  += delta*(x - i.mu)

class Sample:
  "Keep a random sample of stuff seen so far."
  def __init__(i,cache=128):
    i._cache, i.size, i.n = [],cache, 0.0
  def chop(i,bins):
    return chop(sorted(i._cache),bins)
  def __add__(i,x):
    i.n += 1
    if len(i._cache) < i.size : # if cache not full
      i._cache += [x]           # then add
    else: # otherwise, maybe replace an old item
      if random.random() <= i.size/i.n:
        i._cache[int(random.random()*i.size)] = x

def scottknott(data,cohen=0.3,small=3):
  "Split to maximize change in mean."
  def cutHere(parts,all,big,same):
    cut,left,right = None,None,None
    before, mu     =  0, all.mu
    for i,l,r in leftRight(parts):
      if big(l.n) and big(r.n) and not same(l,r):
        n   = all.n * 1.0
        now = l.n/n*(mu- l.mu)**2 + r.n/n*(mu- r.mu)**2  
        if now > before:
          before,cut,left,right = now,i,l,r
    return cut,left,right  
  all  = reduce(lambda x,y:x+y,data)
  same = lambda l,r: abs(l.mu - r.mu) <= all.s*cohen
  big  = lambda    n: n > small    
  return rdiv(data,all,cutHere,big,same)

def rdiv(data,all,div,big,same): 
  "Recursive splits"
  def recurse(parts,all,rank=0):
    cut,left,right = div(parts,all,big,same)
    if cut:  # if cut, rank "right" higher than "left"
      rank = 1 + recurse(parts[:cut],left,rank) 
      rank =     recurse(parts[cut:],right,rank)
    else:  # if no cut, then all get same rank
      for part in parts: 
        part.rank = rank
    return rank
  recurse(sorted(data),all)
  return data

def leftRight(accumulators):
  "For all items, yield everything below,above it."
  # step1: pre-process: accumulate, right to left
  rights = {} 
  n = j = len(accumulators) - 1
  while j > 0:
    rights[j] = accumulators[j]
    if j < n: rights[j] += rights[j+1]
    j -=1
  # step2: output: report left, right accumulation
  left = accumulators[0]
  for i,one in enumerate(accumulators):
    if i> 0: 
      yield i,left,rights[i] 
      left += one # update the left accumulator

def go(f):
  "A decorator that runs code at load time."
  print "\n# ---|", f.__name__,"|-----------------"
  if f.__doc__: print "#", f.__doc__
  f()

#@go
def _leftRight(n=20):
  for lst in [ [11,12,13,14,21,22,23,24,31,32,33,34],
               [11,11,11,11,11,11,11,11,11],
              [1,1,11,11,11,11,11],
              [11,11,11,11,11,11,11,31,32,33,34],
             ]:
    lst1 = lst[:]
    random.shuffle(lst1)
    print rdiv(lst1)
    return 1