n = gets.to_i
s = n.times.map { gets.to_i }
list = [-1]
debug = nil
s.each{|a|
  puts " " if debug
  p "a = #{a}" if debug
  p "list = #{list}" if debug
  # a???list???????°???????????°????????????°?????????????¬????a???
  if list.last < a # list????????????a???????°?????????£??????
    p "if : #{list} << #{a}" if debug
    list << a # list???a????????????, ??¨??????????¢???????
  else # ????°?????¬???\??????a???????????§??????????´????????????°a??¨???????????????
    p "else : i = -2" if debug
    i = -2 # ????????????2??????????????????
    while i >= -list.size and list[i] >= a # ????´?????????????????????????, 
      p "while : #{i} >= #{-list.size} and #{list[i]} >= #{a}" if debug
      i -= 1 # list(?????????????????§??????)????????§a??????????°?????????´????????¢???
      p "i = #{i}"
    end
    p "serch result" if debug
    p i if debug
    i = (0...list.size).bsearch{ |x| list[x] >= a } - 1
    p i if debug
    if list[i] < a and list[i + 1] > a # a???????????§???????????????????????????
      p "if : #{list[i]} < #{a} and #{list[i + 1]} > #{a}" if debug
      list[i + 1] = a
    end
  end
  p list if debug
}
puts list.size - 1