local DBG = false
local function dbgpr(...)
    if DBG then
        io.write("[dbg]")
        print(...)
    end
end

local function dbgpr_t(tbl, use_pairs)
    if DBG then
        local enum = ipairs
        if use_pairs then
            enum = pairs
        end
        dbgpr(tbl)
        io.write("[dbg]")
        for i,v in enum(tbl) do
            io.write(i)
            io.write(":")
            io.write(tostring(v))
            io.write(" ")
        end
        print("")
    end
end


-- binary search
-- https://golang.org/src/sort/search.go?s=2246:2286#L49
local function find_min_true(n, f)
    local function loop(i, j)
        if i == j then
            assert(i >= 1 and i <= n + 1)
            return i
        end
        local h = (i + j) // 2
        assert(h >= 1 and h <= n)
        if f(h) then
            return loop(i, h)
        else
            return loop(h + 1, j)
        end
    end
    return loop(1, n + 1)
end

--
local N = io.read("n")
local A = {}
for i=1,N do
    A[i] = io.read("n")
end

local colors = {} -- descending
local function search(a)
    local function f(i)
        return colors[i] < a
    end
    return find_min_true(#colors, f)
end
table.insert(colors, A[1])

for i=2,N do
    local a = A[i]
    local j = search(a)
    dbgpr_t(colors)
    colors[j] = a -- replace or append to last
    dbgpr(i, a, j, #colors)
end

print(#colors)
