using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;

namespace Competitive
{
    internal class Solution
    {
        public int N;
        public int[] A;

        public void Run()
        {
            // Input
            N = Input.ReadInt();
            A = new int[N];
            for (int i = 0; i < N; i++)
                A[i] = Input.ReadInt();

            var lst = new List<int>();
            for (int i = 0; i < N; i++)
            {
                int lb = LowerBound(lst, A[i]);
                if (lb == lst.Count) lst.Add(A[i]);
                else lst[lb] = A[i];
            }

            Console.WriteLine(lst.Count);
        }

        public int LowerBound(List<int> lst, int x)
        {
            // lower_boundはx以上となる最初の要素のindex
            // upper_boundはxより大となる最初の要素のindex
            // 存在しない場合はlst.Count
            if (lst.Count == 0) return 0;
            var bs = new BinarySearch(lst);
            return bs.Search(x);
        }
    }

    // libs ----------
    internal class BinarySearch
    {
        public List<int> S;
        public int N { get { return S.Count; } }

        public BinarySearch(List<int> s)
        {
            S = s;
        }

        // 左側がfalse, 右側がtrueである必要がある
        public bool Cond(int i, int x)
        {
            if (S[i] >= x) return true;
            return false;
        }

        // 初めてCondがtrueを返すindexを返す
        // 全て条件を満たさない場合はNを返す
        public int Search(int x)
        {
            int left = 0;
            int right = N;

            if (Cond(0, x)) return 0;
            if (!Cond(N - 1, x)) return N;

            while (left + 1 < right)
            {
                int mid = (left + right) / 2;
                if (!Cond(mid, x))
                {
                    left = mid;
                }
                else
                {
                    right = mid;
                }
            }
            return right;
        }
    }

    // common ----------

    internal static class Input
    {
        public static string ReadString()
        {
            string line = Console.ReadLine();
            return line;
        }

        public static int ReadInt()
        {
            string line = Console.ReadLine();
            return int.Parse(line);
        }

        public static int[] ReadIntArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(int.Parse).ToArray();            
        }

        public static long ReadLong()
        {
            string line = Console.ReadLine();
            return long.Parse(line);
        }

        public static long[] ReadLongArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(long.Parse).ToArray();
        }

        public static double[] ReadDoubleArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(double.Parse).ToArray();
        }
    }
    
    internal class Program
    {
        public static void Main(string[] args)
        {
            var s = new Solution();
            s.Run();
        }
    }
}


Measured memory_bytes: 10964