#include <cstdio>
#include <cstring>
#include <cstdlib>
#define MAXN 200005
#define MYINF 1000000000

int main ()
{
    int N;
    static int data[MAXN];
    scanf("%d",&N);
    int i;
    for (i = 0; i < N; i++) scanf("%d",&(data[i]));
    static int a[MAXN];
    static int b[MAXN];
    a[0] = -MYINF; b[0] = MYINF;
    for (i = 1; i <= N; i++) { a[i] = MYINF; b[i] = -MYINF; }
    int l, r, c;
    for (i = 0; i < N; i++)
    {
        l = 1; r = N;
        while (r > l)
        {
            c = (l+r) / 2;
            if (a[c] > data[i]) r = c;
            else l = c+1;
        }
        a[l] = data[i];
    }
    for (i = 0; i < N; i++)
    {
        l = 1; r = N;
        while (r > l)
        {
            c = (l+r) / 2;
            if (b[c] < data[i]) r = c;
            else l = c+1;
        }
        b[l] = data[i];
    }
    l = 0; r = N;
    while (r > l)
    {
        c = (l+r+1)/2;
        char isOK = 0;
        for (i = 0; i <= c; i++)
        {
            if (a[i] < b[c-i])
            {
                isOK = 1;
                break;
            }
        }
        if (isOK) l = c;
        else r = c-1;
    }
    printf("%d\n",l);
    return 0;
}