#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("subsir2.in");
ofstream g("subsir2.out");

const int NMAX = 5e3 + 1;
const int INF = 1e9;

int N, A[NMAX];
int B[NMAX], V[NMAX];

int dp[NMAX];
int Max[NMAX];

static inline int my_min (int a, int b)
{
    return (a < b ? a : b);
}

static inline int my_max (int a, int b)
{
    return (a > b ? a : b);
}

class FenwickTree
{
    int bit[NMAX];

private:
    inline int LSB (int X)
    {
        return (X & (-X));
    }

public:
    inline void Update (int pos, int Val)
    {
        for(int i = pos; i <= V[0]; i += LSB(i))
            bit[i] = my_max(bit[i], Val);

        return;
    }

    inline int Query (int pos)
    {
        int ans = 0;

        for(int i = pos; i >= 1; i -= LSB(i))
            ans = my_max(ans, bit[i]);

        return ans;
    }
} fen;

static inline void Read ()
{
    f.tie(nullptr);

    f >> N;

    for(int i = 1; i <= N; ++i)
        f >> A[i], B[i] = A[i];

    return;
}

static inline void Normalize ()
{
    sort(B + 1, B + N + 1);

    V[++V[0]] = B[1];

    for(int i = 2; i <= N; ++i)
        if(B[i] != B[i - 1])
            V[++V[0]] = B[i];

    for(int i = 1; i <= N; ++i)
        A[i] = (int)(lower_bound(V + 1, V + V[0] + 1, A[i]) - V);

    return;
}

static inline void Solve ()
{
    for(int i = 1; i <= N; ++i)
        dp[i] = 1 + fen.Query(A[i]), fen.Update(A[i], dp[i]);

    return;
}

static inline void Find_Answer ()
{
    Max[N] = A[N];

    for(int i = (N - 1); i >= 1; --i)
        Max[i] = my_max(Max[i + 1], A[i]);

    int ans = INF;
    for(int i = 1; i <= N; ++i)
        if(A[i] > Max[i + 1])
            ans = my_min(ans, dp[i]);

    g << ans << '\n';

    return;
}

int main()
{
    Read();

    Normalize();

    Solve();

    Find_Answer();

    return 0;
}