MAX = 100000
tmp = [ None for i in range(MAX) ]

def mergesort(a,low,hi):
  '''Merge-Sort algorithm for arrays of up to MAX elements'''
  global MAX
  assert 0 <= low <= hi <= len(a) <= MAX
  # conquer phase: do nothing when a[low,hi) has 0 or 1 elements
  if low+1<hi:
    # divide phase: there are at least two elements in a[low,hi)
    mid = low+((hi-low)//2)
    mergesort(a,low,mid)        # solve left half
    mergesort(a,mid,hi)         # solve right half
    merge(a,low,mid,hi)         # merge left and right parts

def merge(a,low,mid,hi):
  '''merge a[low,mid) and a[mid,hi) into a[low,hi) assumming
  that the two parts are sorted in ascending order'''
  global tmp
  # copy a[low,hi) to tmp[low,hi)
  for k in range(low,hi):
    tmp[k] = a[k]
  l,r,k = low,mid,low
  while k!=hi:
    if l==mid:
      # a[low,mid) has been processed
      a[k] = tmp[r] ; r += 1
    elif r==hi:
      # a[mid,hi) has been processed
      a[k] = tmp[l] ; l += 1
    else:
      # there are elements in each part to be processed
      if tmp[l] <= tmp[r]:
        # next element in the left is not worse than next element in
        # the right part: then process next in left part
        a[k] = tmp[l] ; l += 1
      else:
        # element in the left is worse than next element in the right
        # part: then process next in right part
        a[k] = tmp[r] ; r += 1
    k += 1