import std.stdio, std.algorithm, std.conv, std.array, std.string;

int[(10^^5)*2] PS;

void main()
{
    auto N = readln.chomp.to!int;
    foreach (i; 0..N) PS[i] = readln.chomp.to!int;

    {
        auto ps = PS[0..N].dup;
        sort(ps);
        if (ps == PS[0..N]) {
            writeln(0);
            return;
        }
    }

    int min_c, max_c = N;

    while ((max_c - min_c) > 1) {
        auto c = (min_c + max_c) / 2;

        int[] ps;
        foreach (p; PS[0..N]) if (p > c) ps ~= p;

        bool flag;
        int b;
        if (ps.empty) goto ok;

        flag = true;
        b = ps[0];
        foreach (p; ps[1..$]) {
            if (p < b) {
                flag = false;
                break;
            }
            b = p;
        }
        if (flag) goto ok;


        ps = [];
        foreach (p; PS[0..N]) if (p <= (N-c)) ps ~= p;
        if (ps.empty) goto ok;
        b = ps[0];
        foreach (p; ps[1..$]) {
            if (p < b) goto ng;
            b = p;
        }

    ok:
        max_c = c;
        continue;

    ng:
        min_c = c;
        continue;
    }

    writeln(max_c);
}