#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace::std;
//struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
__attribute__((constructor))
void init(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(15);
}
// random_device rd;
// mt19937 mt(rd());
// #include <boost/numeric/interval.hpp>
// #include <boost/numeric/interval/io.hpp>
// #include <boost/intrusive/rbtree.hpp>
// #include <boost/dynamic_bitset.hpp>
// #include <boost/geometry.hpp>
// #include <boost/geometry/geometries/linestring.hpp>
// #include <boost/geometry/geometries/polygon.hpp>
// #include <boost/geometry/geometries/point_xy.hpp>
// #include <boost/math/tools/minima.hpp>
// using boost::math::tools::brent_find_minima;
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// typedef mp::number<mp::cpp_dec_float<256>> cdouble;
// typedef mp::cpp_int cint;

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/priority_queue.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
template<typename T=long long>using pbds=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<typename T=long long>using pbds_map=tree<T,T,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
//template<typename T=long long>using pqueue =__gnu_pbds::priority_queue<T, less<T>,rc_binomial_heap_tag>;
typedef long long lint;
typedef long long ll;
typedef long double ldouble;
typedef vector<lint> vec;
typedef vector<vector<lint>> mat;
typedef vector<vector<vector<lint>>> mat3;
typedef vector<double> dvec;
typedef vector<vector<double>> dmat;
typedef vector<vector<vector<double>>> dmat3;
typedef vector<string> svec;
typedef vector<vector<string>> smat;
typedef vector<vector<vector<string>>> smat3;
typedef vector<pair<lint,lint>> pvec;
typedef vector<vector<pair<lint,lint>>> pmat;
typedef vector<vector<vector<pair<lint,lint>>>> pmat3;
#define rep(i, n) for(lint i = 0; i < (lint)(n); i++)
#define irep(i) for(lint i = 0;; i++)
#define irep1(i) for(lint i = 1;; i++)
#define irep2(i) for(lint i = 2;; i++)
#define rrep(i, n) for(lint i = (lint)(n-1); i >-1; i--)
#define rrepi(i,a,b) for(lint i = (lint)(b-1); i >a-1; i--)
#define repi(i,a,b) for(lint i=lint(a);i<lint(b);i++)
#define rep2(i,a,b,c) for(lint i=lint(a);i>lint(b);i+=c)
#define all(x) (x).begin(),(x).end()
#define PI 3.141592653589793
#define dist(x1,y1,x2,y2) (pow(pow(x2-x1,2)+pow(y2-y1,2),0.5))
#define output(v) do{bool f=0;for(auto i:v){cout<<(f?" ":"");if(i>INF/2)cout<<"INF";else cout<<i;f=1;}cout<<"\n";}while(0);
#define output2(v) for(auto j:v)output(j);
#define _output(v) do{bool f=0;rep(i,v.size()){cout<<(f?" ":"");if(v[i]>INF/2)cout<<"INF";else cout<<v[i];f=1;}cout<<"\n";}while(0)
#define _output2(v) rep(j,v.size()){_output(v[j]);}
#define input(a,n) lint n;cin>>n;vector<lint>a(n);rep(i,n)cin>>a[i];
#define SUM(v) accumulate(all(v),0LL)
#define INF (1LL<<60)
#define IINF (1<<30)
#define EPS (1e-10)
#define LINF 9223372036854775807
//#define MOD 998244353LL
#define MOD 1000000007LL
#define endl "\n"
template<typename T=lint>T in(){return *istream_iterator<T>(cin);}
template<typename T=lint>inline T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T=lint>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
template<typename T=lint>inline T add(T a,T b){return a+b;}
template<typename T=lint>inline T minq(T a,T b){return min(a,b);}
inline bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;}
inline bool chmax(auto& s,const auto& t){bool res=s<t;s=max(s,t);return res;}
vector<lint> dx={-1,1,0,0,1,1,-1,-1};
vector<lint> dy={0,0,-1,1,1,-1,1,-1};

// struct bint{
//     vector<int>v;
//     int base=1000;
//     int b10=3;
//     bool sign=true;
//     bint(vector<int> v,bool sign):v(v),sign(sign){}
//     bint(int val){init(val);}
//     bint(long long val){init(val);}
//     template<typename T>
//     void init(T val){
//         if(val<0){
//             sign=false;
//             val*=-1;
//         }
//         while(val){
//             v.push_back(val%base);
//             val/=base;
//         }
//     }
//     bint operator+(const bint& rhs){return bint(*this)+=rhs;}
//     bint operator-(const bint& rhs){return bint(*this)-=rhs;}
//     bint operator+=(const bint& rhs){
//         v.resize(max(v.size(),rhs.v.size())+1);
//         for(int i=0;i<(int)v.size();i++){
//             if(i<(int)rhs.v.size())v[i]+=rhs.v[i];
//         }
//         move_up();
//         correction();
//         return *this;
//     }
//     bint operator*=(const bint& rhs){
//         return *this;
//     }
//     bint mul(const bint& v2){
//         bint v1=*this;
//         v.resize(v1.v.size()*v2.v.size()-1,0);
//         for(int i=0;i<v1.v.size();i++)for(int j=0;j<v2.v.size();j++){
//             v[i+j]+=v1[i]*v2[j];
//         }
//         v
//     }
//     void move_up(){
//         for(int i=0;i<(int)v.size()-1;i++){
//             if(v[i]<0){
//                 int t=(-v[i])/base+1;
//                 v[i+1]-=t;
//                 v[i]+=t*base;
//             }else{
//                 v[i+1]+=v[i]/base;
//                 v[i]%=base;
//             }
//         }
//     }
//     void correction(){
//         if(v[v.size()-1])return;
//         for(int i=v.size()-2;i>=0;i++){
//             if(v[i]!=0){
//                 v.erase(v.begin()+i+1,v.end());
//                 return;
//             }
//         }
//     }
//     string to_string(){
//         string res;
//         if(sign)res=std::to_string(v[v.size()-1]);
//         else res="-"+std::to_string(v[v.size()-1]);
//         for(int i=(int)v.size()-2;i>=0;i--){
//             ostringstream ss;
//             ss<<setw(b10)<<setfill('0')<<v[i];
//             res+=ss.str();
//         }
//         return res;
//     }
// };
// template<typename T,typename E>
// class scapegoat_tree{
//     struct node{
//         T key;E val;
//         int cnt=1;
//         int dep=0;
//         bool removed=0;
//         node* ch[2]={nullptr,nullptr};
//         node(T key,E val):key(key),val(val){}
//     };
//     using np=node*;
//     np root=nullptr;
//     int count(np t){return t?t->cnt:0;}
//     int depth(np t){return t?t->dep:0;}
//     np update_node(np& t){
//         t->cnt=count(t->ch[0])+(!t->removed)+count(t->ch[1]);
//         t->dep=max(depth(t->ch[0]),depth(t->ch[1]))+1;
//         if(depth(t)>3*(log2(count(t))+1)){
//             rebuild(t,get(t));
//         }
//         return t;
//     }

//     public:
//     void update(T key,E val){update(key,val,root);}
//     void erase(T key){erase(key,root);}
//     int lower_bound(T key){return lower_bound(key,root);}
//     T get_key_by_order(int idx){return get_key_by_order(idx,root);}
//     E get_by_order(int idx){return get_by_order(idx,root);}
//     T get(T key){return count(key)?get_by_order(lower_bound(key)):T();}
//     int count(T key){return get_key_by_order(lower_bound(key))==key;}

//     private:
//     void update(T key,E val,np& t){
//         if(!t)t=new node(key,val);
//         else if(key==t->key&&t->removed){
//             t->removed=0;
//             t=new node(key,val);
//         }
//         else if(key==t->key){
//             t->val=upd(t->val,val);
//         }
//         else if(key<t->key)update(key,val,t->ch[0]);
//         else if(key>t->key)update(key,val,t->ch[1]);
//         update_node(t);
//     }
//     void erase(T key,np& t){
//         if(!t)return;
//         else if(key==t->key)t->removed=1;
//         else if(key<t->key)erase(key,t->ch[0]);
//         else if(key>t->key)erase(key,t->ch[1]);
//         update_node(t);
//     }
//     int lower_bound(T key,np t){
//         if(!t)return 0;
//         if(key==t->key)return count(t->ch[0]);
//         if(key<t->key)return lower_bound(key,t->ch[0]);
//         else return count(t->ch[0])+1+lower_bound(key,t->ch[1]);
//     }
//     T get_key_by_order(int idx,np t){
//         assert(0<=idx&&idx<count(t));
//         if(idx==count(t->ch[0]))return t->key;
//         else if(idx<count(t->ch[0]))return get_key_by_order(idx,t->ch[0]);
//         else return get_key_by_order(idx-count(t->ch[0])-1,t->ch[1]);
//     }
//     E get_by_order(int idx,np t){
//         assert(0<=idx&&idx<count(t));
//         if(idx==count(t->ch[0]))return t->val;
//         else if(idx<count(t->ch[0]))return get_by_order(idx,t->ch[0]);
//         else return get_by_order(idx-count(t->ch[0])-1,t->ch[1]);
//     }
//     void rebuild(np& t,vector<pair<T,E>> v){
//         if(v.size()==0){t=nullptr;return;}
//         int n=v.size();
//         int mid=n/2;
//         t=new node(v[mid].first,v[mid].second);
//         vector<pair<T,E>> v1(mid),v2(n-mid-1);
//         for(int i=0;i<mid;i++)v1[i]=v[i];
//         for(int i=mid+1;i<n;i++)v2[i-mid-1]=v[i];
//         rebuild(t->ch[0],v1);
//         rebuild(t->ch[1],v2);
//         update_node(t);
//     }
//     vector<pair<T,E>> get(np t){
//         if(!t)return vector<pair<T,E>>();
//         auto v1=get(t->ch[0]),v2=get(t->ch[1]);
//         if(!t->removed)v1.emplace_back(t->key,t->val);
//         v1.insert(v1.end(),all(v2));
//         return v1;
//     }
//     E upd(E s,E t){
//         return s+t;
//     }
// };
class mint {
  using u64 = std::uint_fast64_t;
    public:
    u64 a;
    constexpr mint(const u64 x = 0) noexcept : a(x % MOD) {}
    constexpr u64 &value() noexcept { return a; }
    constexpr const u64 &value() const noexcept { return a; }
    constexpr mint operator+(const mint rhs) const noexcept {
        return mint(*this) += rhs;
    }
    constexpr mint operator-(const mint rhs) const noexcept {
        return mint(*this) -= rhs;
    }
    constexpr mint operator*(const mint rhs) const noexcept {
        return mint(*this) *= rhs;
    }
    constexpr mint operator/(const mint rhs) const noexcept {
        return mint(*this) /= rhs;
    }
    constexpr mint &operator+=(const mint rhs) noexcept {
        a += rhs.a;
        if (a >= MOD) {
            a -= MOD;
        }
        return *this;
    }
    constexpr mint &operator-=(const mint rhs) noexcept {
        if (a < rhs.a) {
            a += MOD;
        }
        a -= rhs.a;
        return *this;
    }
    constexpr mint &operator*=(const mint rhs) noexcept {
        a = a * rhs.a % MOD;
        return *this;
    }
    constexpr mint operator++(int n) const noexcept {
        return mint(*this) +=1;
    }
    constexpr mint operator--(int n) const noexcept {
        return mint(*this) -=1;
    }
    constexpr mint &operator/=(mint rhs) noexcept {
        u64 exp = MOD - 2;
        while (exp) {
            if (exp % 2) {
                *this *= rhs;
            }
            rhs *= rhs;
            exp /= 2;
        }
        return *this;
    }
};
ostream& operator<<(ostream& lhs, const mint& rhs) noexcept {
    lhs << rhs.a;
    return lhs;
}
istream& operator>>(istream& lhs, const mint& rhs) noexcept {
    lhs >> rhs.a;
    return lhs;
}
inline mint pow(mint m,lint n){
    if(n==0)return 1;
    else if(n%2==0){
        mint x=pow(m,n/2);
        return x*x;
    }else{
        return m*pow(m,n-1);
    }
}
inline mint fact(lint a){
    return a?fact(a-1)*a:1;
}
int main(){
    lint n;
    cin>>n;
    vec a(n),b(n);
    rep(i,n)cin>>a[i];
    rep(i,n)b[a[i]-1]=i;
    lint cnt=1,mx=1;
    rep(i,n-1){
        if(b[i+1]>b[i])cnt++;
        else {
            chmax(mx,cnt);
            cnt=1;
        }
    }
    chmax(mx,cnt);
    cout<<n-mx<<endl;
}

Measured memory_bytes: 3328