/+ dub.sdl:
    name "A"
    dependency "dcomp" version=">=0.6.0"
+/

import std.stdio, std.algorithm, std.range, std.conv;
import std.numeric, std.math;

// import dcomp.foundation, dcomp.scanner;
// import dcomp.algorithm;

immutable B = 400;

int n, m;
int[] a;

int calc() {
    int R = 0;
    int[] h = new int[2*n+10000];
    int ma = -1;
    long cnt = 0;
    int[] rb = new int[B];
    foreach (p; a) {
        ma = max(ma, p);
        h[p] = 10^^9;
        int getR(int x) {
            while (h[rb[x]] > x) rb[x]++;
            return rb[x];
        }
        void succ() {
            cnt++;
            if (R <= p) return;
            int q = binSearch!(q => h[p+q] <= q)(-1, min(2*n+8-p, h[p+1]));
            h[p+q] = q;
            p += q;
        }
        if (p < R) {
            //first succ
            int q = binSearch!(q => h[p+q] <= q)(0, 2*n+8-p);
            h[p+q] = q;
            p += q;
        }
        //big step
        while (p < R && B <= h[p+1]) {
            succ();
        }
        //small step
        while (p < R) {
//            int same_l = binSearch!(q => h[p+q] != h[p+1])(1, 2*n+8-p)-1;
//            assert(same_l == getR(h[p+1]-1)-1-p);
            int same_l = getR(h[p+1]-1)-1-p;
            p += same_l / h[p+1] * h[p+1];
            succ();
        }
        R = p;
    }
    return R;
}

int solve(int[] p) {
    n = p.length.to!int;
    int[] ma = new int[n];
    ma[] = -1;
    a = new int[n];
    foreach (d; p) {
        auto idx = binSearch!(i => d >= ma[i])(-1, n);
        ma[idx] = d;
        a[d] = idx;
    }
    m = a.maximum + 1;
    reverse(a);
    return calc();
}

int naive(int[] pp) {
    int[] p = pp.dup;
    n = p.length.to!int;
    int cnt = 0;
    bool[] used = new bool[n];
    int[] buf = new int[n];
    while (true) {
        if (equal(p, iota(n))) break;
        cnt++;
        int ma = -1;
        foreach (i, d; p) {
            used[i] = ma < d;
            ma = max(ma, d);
        }
        int c = 0;
        foreach (i; 0..n) {
            if (used[i]) continue;
            buf[c] = p[i]; c++;
        }
        foreach (i; 0..n) {
            if (!used[i]) continue;
            buf[c] = p[i]; c++;
        }
        swap(p, buf);
    }
    return cnt;
}

void test(int n) {
    import std.random;
    auto a = iota(n).array;
    a.randomShuffle;
    writeln(solve(a));
/*    int x = solve(a);
    int y = naive(a);
    if (x != y) {
        writeln(a);
        writeln(x, " ", y);
    }
  */  
}

int main() {
    auto sc = new Scanner(stdin);    
    int dummy;
    int[] p;
    sc.read(dummy, p);
    p[] -= 1;
    writeln(solve(p));
//    test(200000);
/*    foreach (i; 0..10000) {
        import std.random;
        int n = uniform(4, 30);
        auto a = iota(n).array;
        a.randomShuffle;
        int x = solve(a);
        int y = naive(a);
        if (x != y) {
            writeln(a);
            writeln(x, " ", y);
        }
    }*/
    return 0;
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/foundation.d */
// module dcomp.foundation;
 
static if (__VERSION__ <= 2070) {
    template fold(fun...) if (fun.length >= 1) {
        auto fold(R, S...)(R r, S seed) {
            import std.algorithm : reduce;
            static if (S.length < 2) {
                return reduce!fun(seed, r);
            } else {
                import std.typecons : tuple;
                return reduce!fun(tuple(seed), r);
            }
        }
    }
     
}
version (X86) static if (__VERSION__ < 2071) {
    int bsf(ulong v) {
        foreach (i; 0..64) {
            if (v & (1UL << i)) return i;
        }
        return -1;
    }
    int bsr(ulong v) {
        foreach_reverse (i; 0..64) {
            if (v & (1UL << i)) return i;
        }
        return -1;   
    }
    int popcnt(ulong v) {
        int c = 0;
        foreach (i; 0..64) {
            if (v & (1UL << i)) c++;
        }
        return c;
    }
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/scanner.d */
// module dcomp.scanner;

class Scanner {
    import std.stdio : File;
    import std.conv : to;
    import std.range : front, popFront, array, ElementType;
    import std.array : split;
    import std.traits : isSomeChar, isStaticArray, isArray; 
    import std.algorithm : map;
    File f;
    this(File f) {
        this.f = f;
    }
    char[512] lineBuf;
    char[] line;
    private bool succ() {
        import std.range.primitives : empty, front, popFront;
        import std.ascii : isWhite;
        while (true) {
            while (!line.empty && line.front.isWhite) {
                line.popFront;
            }
            if (!line.empty) break;
            if (f.eof) return false;
            line = lineBuf[];
            f.readln(line);
        }
        return true;
    }

    private bool readSingle(T)(ref T x) {
        import std.algorithm : findSplitBefore;
        import std.string : strip;
        import std.conv : parse;
        if (!succ()) return false;
        static if (isArray!T) {
            alias E = ElementType!T;
            static if (isSomeChar!E) {
                 
                 
                auto r = line.findSplitBefore(" ");
                x = r[0].strip.dup;
                line = r[1];
            } else {
                auto buf = line.split.map!(to!E).array;
                static if (isStaticArray!T) {
                     
                    assert(buf.length == T.length);
                }
                x = buf;
                line.length = 0;
            }
        } else {
            x = line.parse!T;
        }
        return true;
    }
    int read(T, Args...)(ref T x, auto ref Args args) {
        if (!readSingle(x)) return 0;
        static if (args.length == 0) {
            return 1;
        } else {
            return 1 + read(args);
        }
    }
}



 

 
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/algorithm.d */
// module dcomp.algorithm;

import std.range.primitives;
import std.traits : isFloatingPoint, isIntegral;

 
T binSearch(alias pred, T)(T l, T r) if (isIntegral!T) {
    while (r-l > 1) {
        T md = (l+r)/2;
        if (!pred(md)) l = md;
        else r = md;
    }
    return r;
}

 
T binSearch(alias pred, T)(T l, T r, int cnt = 60) if (isFloatingPoint!T) {
    foreach (i; 0..cnt) {
        T md = (l+r)/2;
        if (!pred(md)) l = md;
        else r = md;
    }
    return r;
}

 
 

Rotator!Range rotator(Range)(Range r) {
    return Rotator!Range(r);
}

struct Rotator(Range)
if (isForwardRange!Range && hasLength!Range) {
    size_t cnt;
    Range start, now;
    this(Range r) {
        cnt = 0;
        start = r.save;
        now = r.save;
    }
    this(this) {
        start = start.save;
        now = now.save;
    }
    @property bool empty() {
        return now.empty;
    }
    @property auto front() {
        assert(!now.empty);
        import std.range : take, chain;
        return chain(now, start.take(cnt));
    }
    @property Rotator!Range save() {
        return this;
    }
    void popFront() {
        cnt++;
        now.popFront;
    }
}

 
E minimum(alias pred = "a < b", Range, E = ElementType!Range)(Range range, E seed)
if (isInputRange!Range && !isInfinite!Range) {
    import std.algorithm, std.functional;
    return reduce!((a, b) => binaryFun!pred(a, b) ? a : b)(seed, range);
}

 
ElementType!Range minimum(alias pred = "a < b", Range)(Range range) {
    assert(!range.empty, "range must not empty");
    auto e = range.front; range.popFront;
    return minimum!pred(range, e);
}

 
 

 
E maximum(alias pred = "a < b", Range, E = ElementType!Range)(Range range, E seed)
if (isInputRange!Range && !isInfinite!Range) {
    import std.algorithm, std.functional;
    return reduce!((a, b) => binaryFun!pred(a, b) ? b : a)(seed, range);
}

 
ElementType!Range maximum(alias pred = "a < b", Range)(Range range) {
    assert(!range.empty, "range must not empty");
    auto e = range.front; range.popFront;
    return maximum!pred(range, e);
}

 
 

bool[ElementType!Range] toMap(Range)(Range r) {
    import std.algorithm : each;
    bool[ElementType!Range] res;
    r.each!(a => res[a] = true);
    return res;
}


Measured memory_bytes: 11536