#include <fstream>

#define N_MAX 100005

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n, arr[N_MAX], lsi[N_MAX], p[N_MAX];

int binarySearch(int low, int high, int x);
void solve();

int main()
{
    fin >> n;
    for (int i = 0; i < n; i++)
        fin >> arr[i];

    solve();

    return 0;
}

int binarySearch(int low, int high, int x)
{
    while (high-low > 1)
    {
        int mid = low + (high-low) / 2;
        if (arr[mid] >= x)
            high = mid;
        else
            low = mid;
    }

    return high;
}

void solve()
{
    int len = 0;
    lsi[0] = arr[0];
    for (int i = 1; i < n; i++)
    {
        if (arr[i] < lsi[0])
            // new smallest
            lsi[0] = arr[i];
        else if (arr[i] > lsi[n-1])
            // arr[i] extends lsi
            lsi[len++] = arr[i];
        else
            // throw away larger elements
            lsi[binarySearch(-1, n-1, arr[0])] = arr[i];
    }

    fout << len << "\n";
}