{-# OPTIONS_GHC -Wall #-}

import           Control.Monad
import qualified Data.Vector.Unboxed         as V
import qualified Data.Vector.Unboxed.Mutable as M

readInt :: String -> Int
readInt = read

inf :: Int
inf = 1010000000000000000

lowerBound :: V.Vector Int -> Int -> Int -> Int -> Int
lowerBound v x lo hi
    | lo == hi  = lo
    | otherwise = case compare x y of
        GT -> lowerBound v x (mid+1) hi
        _  -> lowerBound v x lo mid
        where
            y   = v V.! mid
            mid = (lo+hi) `div` 2

calcDp :: Int -> V.Vector Int -> V.Vector Int
calcDp n as = res
    where
        res = V.create $ do
            dp <- M.replicate n inf
            forM_ [0..n-1] $ \i -> do
                dp' <- V.unsafeFreeze dp
                let x   = as V.! i
                let lb  = lowerBound dp' x 0 (i+1)
                M.write dp lb x
            return dp

main :: IO ()
main = do
    n  <- fmap readInt getLine
    as <- fmap (map readInt . words) getContents
    let as' = V.fromList as

    let dp  = calcDp n as'
    let ans = lowerBound dp inf 0 n

    --print dp
    print ans

