List of integers & L.I.S.

[antonmuhin]

I hope nobody have posted similar solution (it's tested, but I didn't
submit it to contest):

from bisect import bisect_right as find

def supernumbers(ls):
  indices = [0]*len(ls)
  for i, e in enumerate(ls):
    indices[e - 1] = i

  result = [None]*len(ls)

  borders = []

  for i in indices:
    ind = find(borders, i)
    result[i] = ind + 1
    if ind == len(borders):
      borders.append(i)
    else:
      borders[ind] = i

  return result

At least, it looks shorter than other solutins.
Of course, it allows number of optimizations like
prefetching length and caching borders.append.

If I'm correct, it takes O(n*log (max sequence length)) time that can
be a win for huge datasets.

With the best regards,
anton.