Scanf.scanf "%d" (fun n ->
    let p = Array.init n (fun _ -> Scanf.scanf " %d" (fun p -> p)) in

    let lis = Array.make (n + 1) 0 in
    lis.(0) <- p.(0);

    let rec loop i acc =
        if i = n then acc else
            let rec bin left right =
                if left = right then left else
                let m = (left + right) / 2 in
                if p.(i) > lis.(m) then bin left m
                                   else bin (m + 1) right
            in
            let k = bin 0 acc in
            if k = 0 then loop (i + 1) acc else (
                lis.(k) <- p.(i);
                let acc = if k = acc then acc + 1 else acc in
                loop (i + 1) acc
            )
    in
    loop 1 1 |> Printf.printf "%d\n"
)