let lower_bound (a : int array) first last v =
  let rec doit len first =
    if len = 0 then first
    else
      let half = len / 2 in
      let mid = first + half in
      if a.(mid) < v then doit (len - half - 1) (mid + 1)
      else doit half first in
  doit (last - first + 1) first

let () =
  let n = read_int () in
  let t = Array.make (n + 1) max_int in
  let rec doit i l =
    if i = n then l
    else begin
      let a = read_int () in
      let x = lower_bound t 0 n a in
      t.(x) <- a;
      doit (i + 1) (x + 1)
    end in
  doit 0 0 |> Printf.printf "%d\n"