#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <bitset>
#include <complex>
#include <functional>
#include <limits>
#include <numeric>
#include <string>
#include <tuple>
#include <utility>
#include <array>
#include <vector>
#include <deque>
#include <forward_list>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>

using namespace std;

#define popcount __builtin_popcountll
#define FORS(i, s, n) for (int i = (s); i < (n); ++i)
#define FOR(i, n) FORS(i, 0, n)
#define FI(n) FOR(i, n)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MP(x,y) make_pair((x),(y))
#define PB(x) push_back((x))
#define SZ(c) int((c).size())
#define FOR_SETTED_BIT(bit, mask) for (int bit = 0; (mask) >> bit; ++bit) if (1&(mask >> bit))
#define FOR_NONZERO_SUBMASK(submask, mask) for (int submask=(mask); submask; submask=(submask-1)&(mask))
#define PI (3.141592653589793L)
#define MODULO ((ll)1e9+7LL)


typedef long long ll;
typedef long double ld;
typedef pair < int, int > pi;
typedef pair < ll, ll > pll;
typedef pair < ld, ld > pld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<pld> vpld;
typedef list<int> li;
typedef list<ll> lll;
typedef list<ld> lld;
typedef list<pi> lpi;
typedef list<pll> lpll;
typedef list<pld> lpld;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vld> vvld;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<vpld> vvpld;
typedef vector<li> vli;
typedef vector<lll> vlll;
typedef vector<lld> vlld;
typedef vector<lpi> vlpi;
typedef vector<lpll> vlpll;
typedef vector<lpld> vlpld;
typedef set<int> si;
typedef set<ll> sll;
typedef set<pi> spi;
typedef set<pll> spll;
typedef vector< list < pair < int, ll > > > AdjacencyLists;
typedef vvll AdjacencyMatrix;


template<class T> inline T sqr(const T &x) { return x * x; }
inline ll sqr(int x){return sqr<ll>(x);}
template<class T>T binpow(const T &a, ll n) { return n == 0 ? 1 : sqr(binpow(a, n / 2))* (n % 2 ? a : 1); }
ll binpow(ll a, ll n, ll modulo) { return n == 0 ? 1 : sqr(binpow(a, n / 2, modulo)) % modulo * (n % 2 ? a : 1) % modulo; }

ll gcd(ll a, ll b, ll &x, ll &y)
{
    if (a == 0)
    {
        x = 0;
        y = 1;
        return b;
    }
    ll x1, y1;
    ll d = gcd(b%a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}
inline ll phi (ll n) {
    ll result = n;
    for (ll i=2; i*i<=n; ++i)
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    if (n > 1)
        result -= result / n;
    return result;
}
inline vll inverseAll(ll m)
{
    vll r(m);
    r[1] = 1;
    for (int i=2; i<m; ++i)
        r[i] = (m - (m/i) * r[m%i] % m) % m;
    return r;
}
inline ll gcd(ll a, ll b) { return gcd(a, b, a, b); }
inline ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
inline ll llrand()
{
    const ll lsbToFill = (sizeof(ll) << 3) - 1;
    const ll bitsFilledInIteration = popcount(RAND_MAX);
    ll number = 0;
    
    for (ll lsbFilled = 0; lsbFilled <= lsbToFill; lsbFilled += bitsFilledInIteration)
    {
        number ^= (((ll)rand()) << lsbFilled);
    }
    
    return number & numeric_limits<ll>::max();
}
inline ll llrand(ll begin, ll end)
{
    return begin + llrand() % (end - begin);
}

struct Dinic {
    struct Edge {
        int u, v;
        ll cap, flow;
        Edge() {}
        Edge(int u, int v, ll cap): u(u), v(v), cap(cap), flow(0) {}
    };
    
    int N;
    vector<Edge> E;
    vector<vector<int>> g;
    vector<int> d, pt;
    
    Dinic(int N): N(N), E(0), g(N), d(N), pt(N) {}
    
    void AddEdge(int u, int v, ll cap) {
        if (u != v) {
            E.emplace_back(Edge(u, v, cap));
            g[u].emplace_back(E.size() - 1);
            E.emplace_back(Edge(v, u, 0));
            g[v].emplace_back(E.size() - 1);
        }
    }
    
    bool BFS(int S, int T) {
        queue<int> q({S});
        fill(d.begin(), d.end(), N + 1);
        d[S] = 0;
        while(!q.empty()) {
            int u = q.front(); q.pop();
            if (u == T) break;
            for (int k: g[u]) {
                Edge &e = E[k];
                if (e.flow < e.cap && d[e.v] > d[e.u] + 1) {
                    d[e.v] = d[e.u] + 1;
                    q.emplace(e.v);
                }
            }
        }
        return d[T] != N + 1;
    }
    
    ll DFS(int u, int T, ll flow = -1) {
        if (u == T || flow == 0) return flow;
        for (int &i = pt[u]; i < g[u].size(); ++i) {
            Edge &e = E[g[u][i]];
            Edge &oe = E[g[u][i]^1];
            if (d[e.v] == d[e.u] + 1) {
                ll amt = e.cap - e.flow;
                if (flow != -1 && amt > flow) amt = flow;
                if (ll pushed = DFS(e.v, T, amt)) {
                    e.flow += pushed;
                    oe.flow -= pushed;
                    return pushed;
                }
            }
        }
        return 0;
    }
    
    ll MaxFlow(int S, int T) {
        ll total = 0;
        while (BFS(S, T)) {
            fill(pt.begin(), pt.end(), 0);
            while (ll flow = DFS(S, T))
                total += flow;
        }
        return total;
    }
};

vll Dijkstra(const AdjacencyLists &g, int s)
{
    vll d(SZ(g), numeric_limits<ll>::max() / 2LL);
    priority_queue < pair<ll, int> > q;

    d[s] = 0;
    q.emplace(-0, s);
    
    while (!q.empty())
    {
        while (q.top().first > d[q.top().second]) { q.pop(); }
        int v = q.top().second;
        
        q.pop();
        
        for (const auto &cw : g[v])
        {
            if (d[v] + cw.second < d[cw.first])
            {
                d[cw.first] = d[v] + cw.second;
                q.emplace(-d[cw.first], cw.first);
            }
        }
    }
    
    return d;
}

struct BinarySearchIterator : public std::iterator<std::forward_iterator_tag, bool>
{
    ll value;
    
    typename iterator_traits<BinarySearchIterator>::difference_type operator - (const BinarySearchIterator &it) const { return value - it.value; }
    
    BinarySearchIterator& operator ++() { ++value; return *this; }
    
    bool operator != (const BinarySearchIterator &it) const { return value != it.value; }
    
    bool operator*() const { /*insert code here*/ return true; }
};

template < int ALPHA >
class AhoCorasick
{
public:
    static const int ILLEGAL_INDEX;
    static const int ROOT;
    
    struct Node
    {
        bool leaf;
        int parent;
        int parentCharacter;
        int link;
        
        int next[ALPHA];
        int go[ALPHA];
        int outputFunction;
        
        Node(int parent = ILLEGAL_INDEX, int parentCharacter = ALPHA) :
            leaf(false),
            parent(parent),
            parentCharacter(parentCharacter),
            link(ILLEGAL_INDEX),
            outputFunction(ILLEGAL_INDEX)
        {
            fill_n(next, ALPHA, ILLEGAL_INDEX);
            fill_n(go, ALPHA, ILLEGAL_INDEX);
        }
    };
    
    vector<Node> tree = vector<Node>(1);
    
    AhoCorasick(){}
    AhoCorasick(int maxStatesNumber)
    {
        tree.reserve(maxStatesNumber);
    }
    
    template < class Iterator >
    void add(int length, const Iterator begin)
    {
        int vertex = ROOT;
        
        for (int i = 0; i < length; ++i)
        {
            if (ILLEGAL_INDEX == tree[vertex].next[begin[i]])
            {
                tree[vertex].next[begin[i]] = SZ(tree);
                tree.push_back(Node(vertex, begin[i]));
            }
            
            vertex = tree[vertex].next[begin[i]];
        }
        
        tree[vertex].leaf = true;
    }
    
    int getLink(int vertex)
    {
        assert(0 <= vertex && vertex < tree.size());
        
        if (ILLEGAL_INDEX == tree[vertex].link)
        {
            if (ROOT == vertex || ROOT == tree[vertex].parent)
            {
                tree[vertex].link = ROOT;
            }
            else
            {
                tree[vertex].link = go(getLink(tree[vertex].parent), tree[vertex].parentCharacter);
            }
        }
        
        return tree[vertex].link;
    }
    
    int go(int vertex, int character)
    {
        assert(0 <= character && character < ALPHA);
        assert(0 <= vertex && vertex < tree.size());
        
        if (ILLEGAL_INDEX == tree[vertex].go[character])
        {
            if (ILLEGAL_INDEX == tree[vertex].next[character])
            {
                tree[vertex].go[character] = ROOT == vertex ? ROOT : go(getLink(vertex), character);
            }
            else
            {
                tree[vertex].go[character] = tree[vertex].next[character];
            }
        }
        
        return tree[vertex].go[character];
    }
    
    int getOutputFunction(int vertex)
    {
        assert(0 <= vertex && vertex < tree.size());
        
        if (ILLEGAL_INDEX == tree[vertex].outputFunction)
        {
            if (tree[vertex].leaf || ROOT == vertex)
            {
                tree[vertex].outputFunction = vertex;
            }
            else
            {
                tree[vertex].outputFunction = getOutputFunction(getLink(vertex));
            }
        }
        
        return tree[vertex].outputFunction;
    }
};

template < int ALPHA > const int AhoCorasick<ALPHA>::ILLEGAL_INDEX = -1;
template < int ALPHA > const int AhoCorasick<ALPHA>::ROOT = 0;


ll solve_decrease(const vi &p)
{
    const int n = SZ(p);
    int last_found_number = n + 1;
    
    for (int i = n - 1; i >= 0; --i)
    {
        if (last_found_number == p[i] + 1)
        {
            --last_found_number;
        }
    }
    
    return last_found_number - 1;
}

ll solve_increase(vi p)
{
    const int n = SZ(p);

    FI(n)
    {
        p[i] = n - p[i] + 1;
    }
    
    reverse(ALL(p));
    
    return solve_decrease(p);
}

ll solve_old(const vi &p)
{
    return min(solve_decrease(p), solve_increase(p));
}

vi get_index_to_sequential_forward(const vi &p)
{
    const int n = SZ(p);

    vi index_to_sequential_forward(n, 0);
    
    FI(n)
    {
        index_to_sequential_forward[i] = 0 == i ? 1 : (index_to_sequential_forward[i - 1] * (p[i-1] + 1 == p[i]) + 1);
    }
    
    return index_to_sequential_forward;
}

vi get_index_to_sequential_backward(vi p)
{
    const int n = SZ(p);
    
    FI(n)
    {
        p[i] = n - p[i] + 1;
    }
    
    reverse(ALL(p));
    
    auto index_to_sequential_forward = get_index_to_sequential_forward(p);
    
    reverse(ALL(index_to_sequential_forward));
    
    return index_to_sequential_forward;
}

ll solve(const vi &p)
{
    const int n = SZ(p);
    
    vector < int > sequence_length(1 + n, 0);
    
    FI(n)
    {
        sequence_length[p[i]] = sequence_length[p[i] - 1] + 1;
    }
    
    return n - *max_element(ALL(sequence_length));
    
}

bool aux(const vi &p, int depth)
{
    const int n = SZ(p);
    
    if (is_sorted(ALL(p)))
    {
        return true;
    }
    
    if (0 == depth)
    {
        return false;
    }
    
    for (int i = 0; i < n; ++i)
    {
        vi pp(ALL(p));
        pp.erase(pp.begin() + i);
        pp.insert(pp.begin(), p[i]);
        
        if (aux(pp, depth - 1))
        {
            return true;
        }
        
        pp.erase(pp.begin());
        pp.insert(pp.end(), p[i]);
        
        if (aux(pp, depth - 1))
        {
            return true;
        }
    }
    
    return false;
}

int bf(const vi &p)
{
    for (int depth = 0; ; ++depth)
    {
        if (aux(p, depth))
        {
            return depth;
        }
    }
}

vi generate()
{
    int n = 1 + rand() % 7;
    vi p(n);
    
    for (int i = 0; i < n; ++i)
    {
        p[i] = 1 + i;
    }
    
    random_shuffle(ALL(p));
    
    return p;
}

void stress()
{
    for (int i = 0; ; ++i)
    {
        cerr << i << endl;
        auto p = generate();
        auto a = bf(p);
        auto o = solve(p);
        
        if (a != o)
        {
            
            cerr << SZ(p) << endl;
            FI(SZ(p))
            {
                cerr << p[i] << endl;
            }
            
            assert(false);
        }
        else
        {
            cerr << "OK" << endl;
        }
    }
}

int main(int argc, const char * argv[]) {
#ifdef DEBUG
    assert(2 == bf({1, 3, 2, 4}));
    assert(4 == bf({3, 2, 5, 1, 4, 6}));
    assert(5 == bf({6, 3, 1, 2, 7, 4, 8, 5}));
    assert(5 == solve({6, 3, 1, 2, 7, 4, 8, 5}));
    assert(0 == solve({1, 2, 3}));
    assert(2 == solve({1, 3, 2, 4}));
    assert(4 == solve({3, 2, 5, 1, 4, 6}));
    
    stress();
#endif
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    srand((unsigned int)time(NULL));
    
    int n;
    
    while (cin >> n)
    {
        vi p(n);
        
        FI(n)
        {
            cin >> p[i];
        }
        
        cout << solve(p) << endl;
    }

    return 0;
}


Measured memory_bytes: 1792