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: from bisect import bisect_left
  
  n = int(input())
  A = [int(input()) for _ in range(n)]
  
  
  def LIS(arr):
      dp = [arr[0]]
      for i in arr[1:]:
          if dp[-1] < i:
              dp.append(i)
          else:
              dp[bisect_left(dp, i)] = i
      return len(dp)
  
  
  print(LIS(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"}]