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
  import sys
  
  input = sys.stdin.readline
  
  
  def LIS():
      N = int(input())
      INF = 10000000000
      dp = [INF] * (N + 1)
      for _ in range(N):
          x = int(input())
          dp[bisect_left(dp, x)] = x
      print(bisect_left(dp, INF - 1))
  
  
  LIS()
  
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"}]