output_description: Print the minimum number of colors required to satisfy the condition.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      A_1
      :
      A_N
attempt: import bisect
  
  
  class Deque:
      def __init__(self, src_arr=[], max_size=300000):
          self.N = max(max_size, len(src_arr)) + 1
          self.buf = list(src_arr) + [None] * (self.N - len(src_arr))
          self.head = 0
          self.tail = len(src_arr)
  
      def __index(self, i):
          l = len(self)
          if not -l <= i < l:
              raise IndexError("index out of range: " + str(i))
          if i < 0:
              i += l
          return (self.head + i) % self.N
  
      def __extend(self):
          ex = self.N - 1
          self.buf[self.tail + 1 : self.tail + 1] = [None] * ex
          self.N = len(self.buf)
          if self.head > 0:
              self.head += ex
  
      def is_full(self):
          return len(self) >= self.N - 1
  
      def is_empty(self):
          return len(self) == 0
  
      def append(self, x):
          if self.is_full():
              self.__extend()
          self.buf[self.tail] = x
          self.tail += 1
          self.tail %= self.N
  
      def appendleft(self, x):
          if self.is_full():
              self.__extend()
          self.buf[(self.head - 1) % self.N] = x
          self.head -= 1
          self.head %= self.N
  
      def pop(self):
          if self.is_empty():
              raise IndexError("pop() when buffer is empty")
          ret = self.buf[(self.tail - 1) % self.N]
          self.tail -= 1
          self.tail %= self.N
          return ret
  
      def popleft(self):
          if self.is_empty():
              raise IndexError("popleft() when buffer is empty")
          ret = self.buf[self.head]
          self.head += 1
          self.head %= self.N
          return ret
  
      def __len__(self):
          return (self.tail - self.head) % self.N
  
      def __getitem__(self, key):
          return self.buf[self.__index(key)]
  
      def __setitem__(self, key, value):
          self.buf[self.__index(key)] = value
  
      def __str__(self):
          return "Deque({0})".format(str(list(self)))
  
  
  N = int(input())
  A = [int(input()) for _ in range(N)]
  
  x = Deque()
  
  for i, a in enumerate(A):
      if i == 0:
          x.append(a)
      else:
          r = bisect.bisect_left(x, a)
          if r == 0:
              x.appendleft(a)
          else:
              x[r - 1] = a
  
  print(len(x))
  
problem_description: Statement
  
  You are given a sequence with N integers: A = \\{ A_1, A_2, \cdots, A_N \\}.
  For each of these N integers, we will choose a color and paint the integer
  with that color. Here the following condition must be satisfied:
  
    * If A_i and A_j (i < j) are painted with the same color, A_i < A_j.
  
  Find the minimum number of colors required to satisfy the condition.
samples: [{"input": "5\n    2\n    1\n    4\n    5\n    3", "output": "2\n    \n\nWe can satisfy the condition with two colors by, for example, painting 2 and 3\nred and painting 1, 4, and 5 blue.\n\n* * *"}, {"input": "4\n    0\n    0\n    0\n    0", "output": "4\n    \n\nWe have to paint all the integers with distinct colors."}]