gistfile1.py

import bisect

def insertSort(l, n):
  i = bisect.bisect_left(l, n)
  l.insert(i, n)
  return l

def f(l, minimum=1):
  if len(l) == 0:
    return 0
  if len(l) == 1:
    m = max(l[0], minimum)
    return abs(m - l[0])
    
  medians = []
  sorted_l = []
  for i in l[::-1]:
    sorted_l = insertSort(sorted_l, i)
    medians.append(sorted_l[int((len(sorted_l)-1)/2)])
  medians_min = min(medians)
  index = len(l) - medians.index(medians_min) - 1
  m = max(minimum, medians_min)
  return f(l[:index], m) + sum(abs(x - m) for x in l[index:])