# input: a[0..N) array of numbers
# output: longest increasing subsequence of a[0..N)
#
# solution by DP in O(N^2) time and O(N) space with tabulation in
# lis_tab

def lis_tab(a):
  ans,N = 0,len(a)
  if N!=0:
    tab = [ None for i in range(N) ]
    for n in range(N):
      tab[n] = 0
      for i in range(n):
        if a[i]<=a[n]:
          tab[n] = max(tab[n],tab[i])
      tab[n] += 1
      ans = max(ans,tab[n])
  return ans