# 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 memoization in
# lis_memoization

def aux_memoization(a,n,memo):
  assert len(a)>0 and 0<=n<len(a)
  ans = memo[n]
  if ans==None:
    ans = 0
    for i in range(n):
      if a[i]<=a[n]:
        ans = max(ans,aux_memoization(a,i,memo))
    ans += 1
    memo[n] = ans
  return ans

def lis_memoization(a):
  N = len(a)
  ans = 0
  if N!=0:
    memo = [ None for i in range(N) ]
    for n in range(N):
      ans = max(ans,aux_memoization(a,n,memo))
  return ans