fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val aList = IntArray(n) { 0 }
    (1..n).forEach { aList[it - 1] = readLine()!!.toInt() }
    val ansArray = IntArray(n) { Int.MAX_VALUE }
    var count = 0

    for (i in 0 until n) {
        val a = aList[i]
        if (a > ansArray.getOrNull(count - 1) ?: Int.MAX_VALUE) {
            var l = 0
            var r = count
            var mid = (l + r) / 2
            while (true) {
                if (ansArray[mid] < a && ansArray.getOrNull(mid - 1) ?: Int.MAX_VALUE >= a) {
                    ansArray[mid] = a
                    break
                } else if (ansArray[mid] < a) {
                    r = mid
                } else {
                    l = mid
                }
                mid = (l + r) / 2
            }
        } else {
            ansArray[count++] = a
        }
    }
    println(count)
}