
import Control.Monad
import Debug.Trace

greedy :: [Int] -> [Int] -> Int
greedy [] memo = length memo
greedy (x:xs) memo = greedy xs (bar memo x 0 (length memo )) where
  bar [] val _ _ = [val]
  bar ys val lo hi
    | last ys >= val = ys ++ [val]
    | hi < lo = take lo ys ++ [val] ++ drop (lo+1) ys
    | ys!!mid >= val = bar ys val (mid+1) hi
    | ys!!mid <  val = bar ys val lo (mid-1)
    | otherwise = take mid ys ++ [val] ++ drop (mid+1) ys
    where mid = lo + ((hi-lo) `div` 2)

binarySearch :: [Int] -> Int -> Int -> Int -> Int
binarySearch xs val lo hi
  | hi < lo = -1
  | xs!!mid > val = binarySearch xs val lo (mid-1)
  | xs!!mid < val = binarySearch xs val (mid+1) hi
  | otherwise = mid
  where mid = lo + ((hi - lo) `div` 2)

main = do
  n <- read <$> getLine :: IO Int
  ints <- replicateM n (read <$> getLine) :: IO [Int]
  print $ greedy ints []
