using System;
using System.Numerics;
using System.Linq;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace debug
{
    class main
    {
        static void Main(string[] args)
        {
            //問題クラスを展開
            ProgramE a = new ProgramE();
            a.main();//実行する

        }

    }

    class ProgramA
    {
        public void main()
        {
            //まずは数を代入する
            string input = Console.ReadLine();
            int r = int.Parse(input);

            Console.WriteLine(3 * r * r);
        }
            
    }

    class ProgramB
    {
        public void main()
        {
            string[] input = Console.ReadLine().Split(' ');
            int n = int.Parse(input[0]);
            int D = int.Parse(input[1]);

            int sum = n / (2 * D + 1);

            if (n % (2 * D + 1) == 0)
                Console.WriteLine(sum);
            else
            {
                sum++;
                Console.WriteLine(sum);
            }

        }
    }

    class ProgramC
    {
        public void main()
        {
            string input = Console.ReadLine();
            int n = int.Parse(input);

            var a_array = new List<int>();
            for (int i = 0; i < n; i++)
            {
                string input_a = Console.ReadLine();
                int a = int.Parse(input_a);
                a_array.Add(a);
            }
            int max = a_array.Max();
            int max_i = a_array.IndexOf(max);

            for (int i = 0; i < n; i++)
            {
                if (max_i != i)
                    Console.WriteLine(max);
                else
                {
                    a_array.RemoveAt(max_i + 1);
                    Console.WriteLine(a_array.Max());
                }
            }
        }
    }



    
    class ProgramD
    {
        public void main()
        {
            //
            string input = Console.ReadLine();
            int n = int.Parse(input);
            string[] inputA = Console.ReadLine().Split(' ');
            int[] A = new int[n];
            int[] ans = new int[n];
            for (int i = 0; i < n; i++)
                A[i] = int.Parse(inputA[i]);

            //まずは半分より上を考える（これらは倍数を一つしか持たない）
            for (int i = n / 2; i < n; i++)
            {
                ans[i] = A[i];
            }
            
            //減らしたとき条件が固定されていくので満たすかを確認する
            for (int i = n / 2 - 1; i >= 0; i--)
            {
                int sum = 0;
                //上の固定された条件を見る
                for (int j = i; j < n; j = j + (i + 1))
                {
                    if (j == i)
                        sum += A[j];
                    else
                        sum += ans[j];
                }
                ans[i] = sum % 2;//そこから決める
            }

            int count = 0;

            //全部数えたら確認
            for (int i = 0; i < n; i++)
            {
                if (ans[i] == 1)
                    count++;
            }

            //答え出力
            Console.WriteLine(count);

            for (int i = 0; i < n; i++)
            {
                if (ans[i] == 1)
                    Console.Write(i + 1);
                Console.Write(" ");
            }
        }
    }
    
    class ProgramE
    {
        public void main()
        {
            int n = int.Parse(Console.ReadLine());

            List<long> list = new List<long>();
            List<long> color = new List<long>();

            for (int i = 0; i < n; i++)
                list.Add(long.Parse(Console.ReadLine()));

            color.Add(list[n -1]);

            for (int i = 0; i < n - 1; i++)
            {
                long t = list[n - 2 - i];
                

                //入った数が今までより大きかったら加える
                if (color[color.Count - 1] <= t)
                {
                    color.Add(t);
                    continue;
                }

                //入った数が一番小さい場合は更新
                if (color[0] > t)
                {
                    color[0] = t;
                    continue;
                }

                //一個しかない場合
                if (color.Count == 1)
                {
                    color[0] = t;
                    continue;
                }

                //入った数が小さいなら二分探索でt以下の最大の場所を見つけ、書き換え
                int min = 0;
                int max = color.Count - 1;
                do
                {
                    int temp = (min + max) / 2;

                    if (color[temp] <= t)
                        min = temp;
                    else
                        max = temp;

                }while (min + 1 != max);

                color[max] = t;
               
            }

            Console.WriteLine(color.Count);
        }
    }

}




    

Measured memory_bytes: 17884