N = gets.to_i
as = readlines.map(&:to_i)

lasts = [as.shift]
minimum = lasts.first
maximum = lasts.first

until as.empty?
  current_num = as.shift

  if current_num <= minimum
    lasts.unshift(current_num)
    minimum = current_num
  elsif current_num > maximum
    lasts[-1] = current_num
    maximum = current_num
  else
    target_index = (0..lasts.size-1).bsearch { |i| lasts[i] >= current_num } - 1
    lasts[target_index] = current_num
    # indexが0だった場合にはminimumが変化してる可能性あり
    minimum = current_num if target_index == 0
  end
  # p lasts
end
# p lasts
puts lasts.size
