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: import sys, bisect
  
  input = lambda: sys.stdin.readline().rstrip()
  sys.setrecursionlimit(10**7)
  INF = 10**20
  
  
  def I():
      return int(input())
  
  
  def F():
      return float(input())
  
  
  def S():
      return input()
  
  
  def LI():
      return [int(x) for x in input().split()]
  
  
  def LI_():
      return [int(x) - 1 for x in input().split()]
  
  
  def LF():
      return [float(x) for x in input().split()]
  
  
  def LS():
      return input().split()
  
  
  def lis(a):
      dp = [INF] * len(a)
      for i in a:
          idx = bisect.bisect_left(dp, i)
          dp[idx] = i
      return bisect.bisect_left(dp, INF)
  
  
  def resolve():
      n = I()
      a = [I() for _ in range(n)]
  
      print(lis(a))
  
  
  if __name__ == "__main__":
      resolve()
  
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"}]