output_description: The length of the longest increasing subsequence of A.
input_description: n
      a0
      a1
      :
      an-1
      
      
  
  In the first line, an integer n is given. In the next n lines, elements of A
  are given.
attempt: def LIS(n, a):
      lis = 0
      dp = [0] * n
      dp[0] = a[0]
      for i in range(1, n):
          cur = a[i]
          if cur < dp[0]:
              dp[0] = cur
          elif cur > dp[lis]:
              lis += 1
              dp[lis] = cur
          else:
              idx = find_pos(cur, 0, lis, dp)
              dp[idx] = cur
      return lis + 1
  
  
  def find_pos(target, floor, ceiling, dp):
      while floor < ceiling:
          guess_idx = int(floor + (ceiling - floor) / 2)
          guess_val = dp[guess_idx]
          if guess_val == target:
              return guess_idx
          if guess_val < target:
              floor = guess_idx + 1
          else:
              ceiling = guess_idx - 1
      if dp[floor] < target:
          return floor + 1
      return floor
  
  
  n = int(input())
  a = [0] * n
  for i in range(n):
      a[i] = int(input())
  print(LIS(n, a))
  
problem_description: Longest Increasing Subsequence
  
    
  
  For a given sequence A = {a0, a1, ... , an-1}, find the length of the longest
  increasing subsequnece (LIS) in A.
  
  An increasing subsequence of A is defined by a subsequence {ai0, ai1, ... ,
  aik} where 0 ≤ i0 < i1 < ... < ik < n and ai0 < ai1 < ... < aik.
samples: [{"input": "5\n    5\n    1\n    3\n    2\n    4", "output": "3"}, {"input": "3\n    1\n    1\n    1", "output": "1"}]