import java.io.*
import java.lang.*
import java.util.*

val sc = FastScanner()
val pw = PrintWriter(System.out)
const val MOD = 1000000007L
const val INF = 2147483647
const val LINF = 9223372036854775807L

fun main(args: Array<String>) {
    solve()
    pw.flush()
}


fun solve() {
    val n = nextInt()
    val a = nextIntAry(n)
    if(a.distinct().count() == 1){
        println(n)
        return
    }

    val list = intList()
    list.add(a[0])

    for (i in 1 until n){
        val num = a[i]
        var ok = -1
        var ng = list.size
        while(abs(ng - ok) > 1){
            val mid = (ok + ng) / 2
            if(list[mid] < num) ok = mid
            else ng = mid
        }
        when{
            ok >= list.size -> list.add(num)
            ok < 0 -> list.add(0, num)
            else -> list[ok] = num
        }

    }

    println(list.size)

}



fun println(v: String) {
    pw.println(v)
}
fun print(v: String) {
    pw.print(v)
}

fun next() = sc.next()
fun nextInt() = sc.nextInt()
fun nextLong() = sc.nextLong()
fun nextDouble() = next().toDouble()
fun nextAry(n: Int): Array<String> {
    val ary = ary(n)
    for (i in 0 until n) ary[i] = next()
    return ary
}
fun nextIntAry(n: Int): IntArray {
    val ary = intAry(n)
    for (i in 0 until n) ary[i] = nextInt()
    return ary
}
fun nextLongAry(n: Int): LongArray {
    val ary = longAry(n)
    for (i in 0 until n) ary[i] = nextLong()
    return ary
}
fun nextDoubleAry(n: Int): DoubleArray {
    val ary = doubleAry(n)
    for (i in 0 until n) ary[i] = nextDouble()
    return ary
}

fun ary(n: Int, init: String = "") = Array(n) { init }
fun intAry(n: Int, init: Int = 0) = IntArray(n) { init }
fun longAry(n: Int, init: Long = 0L) = LongArray(n) { init }
fun doubleAry(n: Int, init: Double = 0.0) = DoubleArray(n) { init }
fun ary2(n: Int, m: Int, init: String = "") = Array(n) { Array(m) { init } }
fun intAry2(n: Int, m: Int, init: Int = 0) = Array(n) { IntArray(m) { init } }
fun longAry2(n: Int, m: Int, init: Long = 0) = Array(n) { LongArray(m) { init } }
fun doubleAry2(n: Int, m: Int, init: Double = 0.0) = Array(n) { DoubleArray(m) { init } }
fun ary3(n: Int, m: Int, k: Int, init: String = "") = Array(n) { Array(m) { Array(k) { init } } }
fun intAry3(n: Int, m: Int, k: Int, init: Int = 0) = Array(n) { Array(m) { IntArray(k) { init } } }
fun longAry3(n: Int, m: Int, k: Int, init: Long = 0L) = Array(n) { Array(m) { LongArray(k) { init } } }
fun doubleAry3(n: Int, m: Int, k: Int, init: Double = 0.0) = Array(n) { Array(m) { DoubleArray(k) { init } } }
fun list() = mutableListOf<String>()
fun intList() = mutableListOf<Int>()
fun longList() = mutableListOf<Long>()
fun doubleList() = mutableListOf<Double>()
fun strSet() = mutableSetOf<String>()
fun intSet() = mutableSetOf<Int>()
fun longSet() = mutableSetOf<Long>()
fun doubleSet() = mutableSetOf<Double>()
fun <E, V> map() = mutableMapOf<E, V>()

fun Int.a() = this.toLong()
fun Long.a() = this.toInt()
fun IntArray.cumsum(): IntArray {
    val s = intAry(this.size + 1)
    for (i in this.indices) s[i + 1] = s[i] + this[i]
    return s
}
fun LongArray.cumsum(): LongArray {
    val s = longAry(this.size + 1)
    for (i in this.indices) s[i + 1] = s[i] + this[i]
    return s
}
fun MutableMap<String, Int>.counting(n: Int) {
    repeat(n){
        val a = next()
        if(this.containsKey(a)) this[a] = this[a]!! + 1
        else this[a] = 1
    }
}
fun MutableMap<Int, Int>.intCounting(n: Int) {
    repeat(n){
        val a = nextInt()
        if(this.containsKey(a)) this[a] = this[a]!! + 1
        else this[a] = 1
    }
}
fun MutableMap<Long, Int>.longCounting(n: Int) {
    repeat(n){
        val a = nextLong()
        if(this.containsKey(a)) this[a] = this[a]!! + 1
        else this[a] = 1
    }
}


fun abs(n: Int): Int = Math.abs(n)
fun abs(n: Long): Long = Math.abs(n)
fun abs(n: Double): Double = Math.abs(n)
fun max(vararg values: Int) = if (values.isEmpty()) -INF else values.max()!!
fun max(vararg values: Long) = if (values.isEmpty()) -LINF else values.max()!!
fun min(vararg values: Int) = if (values.isEmpty()) INF else values.min()!!
fun min(vararg values: Long) = if (values.isEmpty()) LINF else values.min()!!
tailrec fun gcd(a: Int, b: Int) : Int = if(a % b == 0) b else gcd(b, (a % b))
tailrec fun gcd(a: Long, b: Long) : Long = if(a % b == 0L) b else gcd(b, (a % b))
fun lcm(a: Int, b: Int) : Int = a / gcd(a, b) * b
fun lcm(a: Long, b: Long) : Long = a / gcd(a, b) * b
fun modpow(a: Long, n: Long, p: Long = MOD): Long {
    var res = 1L
    var ar = a
    var nr = n
    while (nr > 0) {
        if ((nr and 1) == 1L) res = res * ar % p
        ar = ar * ar % p
        nr = nr shr 1
    }
    return res
}
fun modinv(a: Long, p: Long = MOD) : Long = modpow(a, p - 2, p)
fun ncr(n: Long, r: Long): Long {
    var a = 1L
    var b = 1L
    for (i in 1..r) {
        a = a * (n + 1 - i) % MOD
        b = b * i % MOD
    }
    return modinv(b, MOD) * a % MOD
}

class Combination(private val max: Int) {
    private val fac = LongArray(max)
    private val finv = LongArray(max)
    private val inv = LongArray(max)
    private val p = MOD.a()
    fun init() {
        fac[0] = 1
        fac[1] = 1
        finv[0] = 1
        finv[1] = 1
        inv[1] = 1
        for (i in 2 until max) {
            fac[i] = fac[i - 1] * i % p
            inv[i] = p - inv[p % i] * (p / i) % p;
            finv[i] = finv[i - 1] * inv[i] % p
        }
    }

    fun com(n: Int, r: Int): Long = if (n < r || (n < 0 || r < 0)) 0 else fac[n] * (finv[r] * finv[n - r] % p) % p
}

class Permutation(private val n: Int, private var searched: Int = 0, private var nextIndex: Int = 0) {
    private val size = fact(n)
    private val permList = Array(size) { IntArray(n) { 0 } }

    private tailrec fun fact(n: Int, ans: Int = 1): Int {
        return if (n == 0) ans
        else fact(n - 1, ans * n)
    }

    fun init() {
        create(0, IntArray(n) { 0 }, Array<Boolean>(n) { false })
    }

    private fun create(num: Int, list: IntArray, flag: Array<Boolean>) {
        if (num == n) {
            permList[searched] = list.copyOf()
            searched++
        }
        for (i in 0 until n) {
            if (flag[i]) continue
            list[num] = i
            flag[i] = true
            create(num + 1, list, flag)
            flag[i] = false
        }
    }

    fun hasNext(): Boolean {
        return if (nextIndex < size) {
            true
        } else {
            nextIndex = 0
            false
        }
    }

    fun nextPerm(): IntArray = permList[nextIndex++]
}


data class Node(val id: Int, var past: Int = -1, val edges: MutableList<Edge> = mutableListOf())
data class Edge(val from: Int, val to: Int, val cost: Long = 1L)

fun dfs(nodes: Array<Node>, now: Int, seen: Array<Boolean>) {
    seen[now] = true
    for (edge in nodes[now].edges) {
        if (seen[edge.to]) continue
        dfs(nodes, edge.to, seen)
    }
}

fun bfs(nodes: Array<Node>, start: Int): LongArray {
    val queue = ArrayDeque<Int>()
    queue.add(start)
    val dist = longAry(nodes.size, -1L)
    dist[start] = 0L
    while (queue.isNotEmpty()) {
        val now = queue.poll()
        for (edge in nodes[now].edges) {
            if (dist[edge.to] != -1L) continue
            dist[edge.to] = dist[now] + 1
            queue.add(edge.to)
        }
    }
    return dist
}

fun dijkstra(nodes: Array<Node>, start: Int): LongArray {
    val queue = PriorityQueue(16) { e1: Edge, e2: Edge ->
        return@PriorityQueue when {
            e1.cost < e2.cost -> -1
            e2.cost > e1.cost -> 1
            else -> 0
        }
    }
    queue.add(Edge(start, start, 0L))
    val dist = longAry(nodes.size, LINF / 2)
    dist[start] = 0
    while (queue.isNotEmpty()) {
        val now = queue.poll()
        if (dist[now.to] < now.cost) continue;
        for (edge in nodes[now.to].edges) {
            if (dist[edge.to] <= dist[edge.from] + edge.cost) continue
            dist[edge.to] = dist[edge.from] + edge.cost
            queue.add(Edge(edge.from, edge.to, dist[edge.to]))
            nodes[edge.to].past = edge.from
        }
    }
    return dist
}

class UnionFind(size: Int){
    private val par = IntArray(size) { it }
    private val size = IntArray(size) { 1 }
    fun root(x: Int) : Int {
        return if(par[x] == x){
            x
        } else {
            par[x] = root(par[x])
            par[x]
        }
    }
    fun same(x: Int, y: Int) : Boolean = root(x) == root(y)
    fun unite(x: Int, y: Int){
        var a = root(x)
        var b = root(y)
        if(a == b) return
        if(size[a] < size[b]){
            var tmp = a
            a = b
            b = tmp
        }
        size[a] += size[b]
        par[b] = a
    }
    fun size(x: Int) : Int = size[root(x)]
}

class FastScanner {
    private val sin: InputStream = System.`in`
    private val buffer: ByteArray = ByteArray(1024) { 0 }
    private var ptr = 0
    private var buflen = 0

    private fun hasNextByte(): Boolean {
        return when {
            ptr < buflen -> true
            else -> {
                ptr = 0
                buflen = sin.read(buffer)
                if (buflen <= 0) false
                true
            }
        }
    }

    private fun readByte(): Int {
        return when {
            hasNextByte() -> buffer[ptr++].toInt()
            else -> -1
        }
    }

    private fun isPrintableChar(c: Int) = c in 33..126

    fun hasNext(): Boolean {
        while (hasNextByte() && !isPrintableChar(buffer[ptr].toInt())) ptr++
        return hasNextByte()
    }

    fun next(): String {
        if (!hasNext()) throw NoSuchElementException()
        val sb = StringBuilder()
        var b = readByte()
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b)
            b = readByte()
        }
        return sb.toString()
    }

    fun nextLong(): Long {
        if (!hasNext()) throw NoSuchElementException()
        var n = 0L
        var minus = false
        var b = readByte()
        if (b.toChar() == '-') {
            minus = true
            b = readByte()
        }
        if (b.toChar() !in '0'..'9') throw NumberFormatException()
        while (true) {
            when {
                b.toChar() in '0'..'9' -> {
                    n *= 10
                    n += b.toChar() - '0'
                }
                b == -1 || !isPrintableChar(b) -> return if (minus) -n else n
                else -> throw NumberFormatException()
            }
            b = readByte()
        }
    }

    fun nextInt(): Int {
        val nl = nextLong()
        if (nl !in Int.MIN_VALUE..Int.MAX_VALUE) throw NumberFormatException()
        return nl.toInt()
    }
}

Measured memory_bytes: 38732