/*
9999G99X999999999999999X9X999X9X9X9X9X9X999X9X9X99999999G9GX99G9GG9S9M9SS9SHG9G9GGGG999999G99X9X9999999X99999X99999X999X9X999X9X99999999999X999X999X99
9XX9X9XXX9XXSXSXSSSXSXSXSXSXSSHSHXSXSXXXSXSXSXX9SXX99X522sssrsrrrsr:isirrrrH9SX9XHsss25S2X59SX99999XXXX9XXX9X9S9SXSXSXSSSXSXS9XXSXSXSXX9SXXXSXSXSXSXSS
9X99999X999X9X9S9X9X9X9X9X9X9X9X9XXSXX9XXX999X9X9SXXXssiiii:i::::,: ,,,,,,:irisrri::i;riss2SXSSSXSGGGG9X9X9X9X9X99999X9X9X9X9X9999999X9X9X9X999X9X9X9S
9X99X999X999X9X9X9X9X9X9X9X9X9SXXXX9X9X9X99GX222sriii::::i:ii;irrri:,,,,,,,,,,,,,:,:::,:::iirri;i;rs299G99999XH9S999S9X9X9X9XXSXX9X999X9X9X9X9X99999XX
9S9X999X9X9XXS9X9XXX9XXX9X9X9S9X9X9XXX9X9XXXHsr:::::,,,:::::irrssssr:,:,::,,:,:::::::::::::,:,:,:,,,:isHX9G9XS9X9SXX9XXX9XXSXX9X9X9X9X9X999X9999999X9S
XX9999X999X9X9X9X9S9X9X9X9SXXXX9X9SXX9X999SSsr:::i:::,,,,,,::;rss2si::,::i:::::::iiii::iii:i:i::::::,,,::;rss5SHXXX9XHX9X9X9X999X9X9X999X9X999X9X9X9XX
9X9X9X9X9X999X9X9XXX9X9X9X9SXX9X9X9X9X99X9Xr:::ir:, ,,,,,,,:iirsssr:iii:::i:::i:iiiii:i:iiriiii:i::::,,,, ,,:::issSSHSG99X9999999X9999999999999X999X9X
99X9X999X9X9X9X9999999X9X9X9X9X9X9S9XX99X9s::i;ri:,,,,,,::rssssririiiiiiiiiiiiiiiii;iiii;;iriii;iiii::::,,,:ii::::irsX999999XX99X9X99999X999999999X9X9
9X999X9X9X9X9X9X99999X9SXX9S9X9X9X9X9XX99s,:rrsrrri::::;ss252ss;iiiiriiiiiiirrrrrir;rirrr;ii;iiiiiii::i:::iissrri::,:is2SH9X9X9X9X9X999X9X99999999999X
9X99X99999X9X999X999X9X9XX99S9XXX9X9X9X9s::rrsssssrrrsssssrssrirrr;r;;iiiiirrrrrrri;:iirrriirrir;riiii:::::irssrrr;i::,:is2999X9X9X99999X9999999X99999
9X9999999X99999XXX99999X9X999X9X9X9X99G9s:irss22sssss25siirrrrrir;ri;iii;rrrr;;;rii::iiriiiiiirrri;i;ii:::::rssssrri;i:,,:sSG99X9X9X9X9X999999999X9999
9XX9X99999XXX9X9S9X999X9X9X9SXS9S9XX9GSs:irsrssSHSH5ssrrrsssrrrrrr;;ii;rrri;iii;ii::ii:;rriiirii;r;;i;iiii:::;ssr;iiiiii:,,r9G99X9X999X9999999X9999999
9S999X9X9X9X9X9X999X9X9X9X9X9SXSXX9XGXr:irsssssssrrs25S22ssrrrrrrrrrrrr;ririiiri:ii:i:iirii:;iirrrrrr;ririi:iirii::ii:ii;:,:2S99999X9X9X9X9999999X9999
XXX9X9999999X9X9X9X9X9X9X999XXXXX9X99s:irsssssssr;r2522srr;rirrrirrr;rrrrri;irir:iiriir;ii:::ii;i;rrrrrr;iiiiiir;i:::::iii:,:s255XX9999999999G9G9G9G99
9S9999G9G9999X9X9X9X9X9X999X9X999X999i:irrsssssr;r22ssrrri;irrrrriii;irrr;rrr;ri;iriiiri::iii:iii:iirrrrrrr;;iiirrr;::iii;i,isHS9X9X9X999999G9G99999G9
9X99999G99X999X9XXXXX9X999X9X999999Gsi:rrrsss22ssssri;irir;rrririi:r;ririiirirrrirriiriiiriri;iiii;rrrssrrrrrriiirssrrirrri:rSS9XXX9X99G9G99999G9G9GGG
9S9999999X9X9X9X9S9X9X9XXXXX999X99G92iirrrss2sssrrri;iiirir;;iiiiirirrr;;irirrrrrri;riiir;i:iirir;r;rrrrsssrrri:i:;rssssssr:sSXX99G9GGGGMGMGGGGGMGMMMG
XX99999G99999999X9X9S9X9X9X99999X99GXrirssssrii::iiiirrrrrrrirrrirrrrrisrr;i;rrrrrrsriirr;ir;rriiiiiiiirrrrsrrrrr;iis222ssriH@M@B@B@B@@@B@B@B@MMMGGG9X
9S999999G99X9X999X9X9X9X9XXXXX999X99Sirsssr::,::i;rirrrrrrri;rrrrrrirrrirrrr;irrrrrr;;rrrrrrrri;rriii:ii;rrrrrrii:i;s2S22srrMB@B@B@B@B@B@B@BBMMGG999XH
999999999999X999X9XXSXSXSXS9X9X9S99G9srr;i:::::i:iiiirriiiirirrri;rrrsrrrsrssrrrrrrrrsssrrrrrirr;rrrrriiirrrrrrr;;irrs22ssr9B@B@B@B@BBMBMBBBMBMMGG99XX
999999G9G9999X9X9X9SXX9X9X9SXX9X9X9X2::::::i;i::::riiirrrrrrrirrrrrrrrrrrrrrsrsrsssrsssrrrsrrrrrrrrrri;i;iiirrrir;r;;isssrrX@BBB@BBMBBBMBMBB@BBMMGG99S
999G999G9999X9X9S9X9SXSXSXSXX9XXX9X9Hi,:,::i:::::ii;iririri;irrsrrrrrrrsrrrssrssrrrrrsrrssrsrrrri;rrrrrrrri;;rrriiiiiirsr;sMBBM@B@MBMBMBMBMBB@BBMMGG99
9X9X9X99999X9XXSXS9XXXXSXX9999GGGGGBBi,,::::::::::iii:i;r:iirrrrsrrrsrsrsssssrrrssrrrrsssrrssrrrrrrrrirrrii:::ii;ii:i:;ss;2M@B@BBBBMBMBMBMMMBBBBBMBMMG
99X9X9999999999G9GGGGGGGGMMBB@B@B@B@M,,,,:::,:,::::iiiiri;;;i;riir;rrsssrss2srssrrsrisrrrsssssrrrrrsrrr;iiii:::i:ii::::i;;S@B@B@BBMBB@MBMBM@MBM@B@@@BM
MGMGMGMMBMBMBB@B@B@B@B@B@B@B@B@B@B@Si,,,:,,,,,,,:::irrrrrrrrr;rii;rrsssssrssrsrrrssrssrrrrsssrssssrrrrririiiri;ii:::::::,r@B@B@B@BBBBB@@@BBB@B@@@B@B@B
B@B@B@B@B@B@B@B@B@B@B@B@B@B@@@MGGSi  ,,,,,,,,,,,,::rrsrrrrrri;iiirrs29995srrrs;rsssrssrrrrrrrrrsssssssrrrririiirr;:i:i:: r@@@@B@B@B@B@B@BBMBMBMMMMMMGG
@B@B@@@B@@@B@B@B@B@B@B@B@G2ri:,,:    ,,,,,,,,,,,:::iirrrsssr;irsss2XG9GGXsss2sss222srrsssr;irrrrsrrrrrrrrrrrrrrrrr;::::, s@B@B@B@MBMMMMMMGMGG9999XX5Hs
B@@@B@B@B@B@B@BMMBB@B@B@Ss:,        ,,,,,,,,,,,,:::iiii;rsrrrss22222ss2925S999S2S92srrsrr;rri;rsssrrirrsrrrsrrrrii:i::,,i@BBMMMMGMGG99999XSXHS5222ssss
@BMGGGBB@B@B@MM999GM@B@M2i:,   ,, ,,,,,,,,,,,,,,::::iirsss22ssrrrii:i;2sssssHX9X925ssirrr:iirrrssssrr;rrrrrrrrrrrii::,,:M@BMMGGGG99X9XS5S5H2522s2s2sss
BM9G9MMBB@B@B@BGX9SX5S2sri,,,,,,,,,, ,,,,,,,,,,,,::i;ss22H2s;irrrssS9SXHsssssH2S22sS2ss2sssss2sssrrsrr;r;rirrrrrrii:,,,5B@MG9G9999X9HX5S222222sssssssr
@BMGGGMM@B@B@BM92ssii::,,,,,,,,,, ,   ,,,,,,,,,,,::irrrirrr;sXBB@B@B@BBG9SG52s2SS2SSXXXSS52ssssssssssrrrsrrrssrrri:,,,,rSG9XXSS2H2222ssssssrrrr;ri;i;:
MMG99XX9XX2H22ssri:,,,,,,,,,           ,,,,,,,,,::::::::::,,rMB@B@9G@@BBSGMM2s2HHSs52Xsrrrrss2222SX2s222ssssrrrrr;:::,,,,:rsssrrrriri;iii:::::,:,:::,,
X5S22ssssrrrriiii::,::i:,,,   ,,,       ,,,,,,:::::,,,,,::,,:2MB@B@B@B@95MM92sSSXH2ss59ss2SGBB@BBB@@M999S2sssssrsri:i::,, ,::::::,:::,:,:,:,,,,,,,,,,,
22ssssssssrsrrrrrrrs22i,,,,,,,,,,,,,,,,,,,,,,,,,,,,, , ,,::::isMB@@@BM22B@MGXSGM995sr2B@B@9GB@B@B@BM9Ssss222ssri:i::,,,,,,,,,,,,,,,,,,,:,,,,,,,,,,,::,
9HXSSSXS9X9999GGMB@@X:, , ,,,,,,,,,,,,,,,,,,,,,,,,,,, , ,,,,::ir22SXSHB@@M9MMGM99S2rrsMBBMrr@B@B@B92srrssssrrri,:,,       ,,,,,,,,,,,,:,,,,,,,,,,,,,,,
BBB@B@B@B@@@B@B@B@Gs   , ,   , , ,,,,:,:,,,,,,,,,,,,,,,,,,,,,,,,:isS992srrii:iir::i;;sS9MMGGB@BG5srrirrri:::,,,,           ,,:,,,,,,,,,,,,,,,:,,,,,,,,
@B@B@@@B@B@B@B@B9:              , ,,,,::i::,,,,,,,,,,,,,,,,,,,,,,:sri, ,,,,,,:::i:,,:::rSMG55srii;r:ii:,,,,                 ,,,,,,,,,,,,,,,,,,,,,,,,,,
@@B@B@MBMMMMGM9r                   ,,,:i:iri,,,,,,,:::,:,,,,,,,,::,,,,,,,,,:::,,,,,,,i::,rGSsrii:::::,,,                   ,,,,,,,,,,,,,,,,,,,,,,,,:,,
G99SS5522s2ssi                      ,,::rrss:,, ,,::i:i,,,:,,:rsrir:,,:,is2SX5sssr:,,,:,,,r92i:,,:i,,                      ,,,:,,,:,:,,,:,,,,,,,,,,,,
srrrrrrrrrrr:      ,                 ,,;srs2sssr:,,::iii:i:::rri:i:, ,,:sM9X2s5H2GG2:,,,,,,r25ssss,                        ,,:,,,,,,,,,,,,,,,,,,,,,,,
i:i:ii;ii:i:                      , ,,,:sss2SS99Hr:,:iri;:::i:,,, ,    ,s9SBBs2s99XMr ,,,,;rs9X9s:,                        ,i,,,,,,,,,,,,,,,,,,,, ,,,
:::i:i:::::,                       ,,,,:is25HHS9992r:::i:iii,,,,    ,,  :MM@MG9GBM92,  ,,irsssS9i,     ,      ,,       ,  ,;::,,,:,,,, ,,,,,,,,,,, ,,,
:,:::,::::,                       ,,,,:::r2SSH99MM@MXsi:::i:i:, , ,     ,9@BMMMM@BS,,   ,,irirXM2,        :r:,,,:;:  ,issrsr:,,,,,, ,,,,,,,,, ,,,,,,,
:,,:,:,,,:,                      ,,,,,:r:rS99GM@@@B@M9sii:,,:i:,,  , , ,isXM@@MBM2,:,, ,,,,,:5M@BBHi,ri,,iX9r:::rMS22GSssr,      ,  ,,,,,,,,,,,,,,,,,,
:,:,,,:,,,,                     , , ,,iir2BB@BBMGsrrrrsssri:::iii::,::irsssrsssii:,,, ,,,:isGBM9229929S;2GMssir;;rri,,      ,,,  ,,,, ,,, ,,,,,,,,,,,
:,:,,,,:,:,                    ,  ,,,isSG@BM92sri::irssSSX25HHS9XSH9X22HSG9BG9XXXSssssrrrssr:,     ,                     ,,,,,,,,,,,,,       ,,,,,,,
,,,,:,,,,,:                 , ,  ,:i5GM9Hr:,,,,,,,,,::::::iisrss2s299XS9G9GGSS92ss2sr,,,,             ,    ,, ,  ,,  ,,,, ,    ,, ,,, ,,,   ,,,,,,  ,
:,,:,,,,,,:, ,,,       ,:, ,:;sssXss2s:        , ,     ,             ,,                  , , , ,,,,,,, , , ,,, ,,,,,   ,,,  ,, ,,,   ,,, , ,   ,,, ,,,
, ,,,,:,:,:irsX2srsssrr2S22ssss:ii,       , , , ,,, ,,, ,,    , ,                   , ,,, , , ,,,  ,,,   ,,  ,,,, , ,,,,,,,,, , ,,, ,,,   ,,, ,,,,,,,,
, ,:,,,,,,,,:i:i;r;r::,,,,,,         ,,,,,,,,,,, ,,,,,  ,,,,  ,, , ,,, ,, ,  , , , ,  ,, ,,,,,,, ,,,,,    ,, ,    ,,,,,,,, , ,,, ,,,,, ,,, ,,,,, ,:,,
, ,,,,,,,,,,                    , ,,,,,,,,, ,,, ,,,,, ,  ,,, ,,,, ,      ,, , ,,,, ,, , , ,,  ,    ,, , ,  ,,,, ,,,   ,,, ,,, , ,,,   ,,, ,,,,, ,,,,,,
, ,,,,,,,,,,,,,,,,,, , ,,, ,,,,,,, ,,,  ,, ,, ,, ,,,   ,,,,,  ,, ,   ,,,,, , ,,  ,     ,,    , ,,, ,,,,, ,,, ,,,,,   ,,, ,,,,,,,,, ,,,,,,,,,,, ,,,,,,,
, ,,,,,,,,,,, , ,,,,,,, ,,, ,,,,,,, ,   ,   ,,,,,,, ,,,,, ,   , ,  ,,   ,       ,   , ,,,,,   , ,   ,,,,,,, ,,,,    ,,  ,,  ,,,,,,, , ,,,,,,,, ,, ,,,
,  ,,,,,,,,, ,,,,,,,,, ,,, ,,,   ,,,,, ,,, , , , ,,  ,,,    ,, ,, ,,       , , ,,,,, ,,, ,,, ,         , , ,     , , ,  ,, ,,, ,,,,,  ,,,,,,,, ,, ,,,
, ,,,,,,, ,,,,, ,,, , ,,  ,,, , ,,,,, ,  ,,,,  ,,   , ,,, , ,       ,   , ,     , , , ,   , , , ,,, , , , , ,,, ,,, ,,, ,,,,  ,,,,,,,,,,, ,,,, ,, ,,,
, ,,,,,,,,,,,,,,,,,,,,,  ,,,,,,, ,,    ,,,   , ,,,,, ,  ,,,, , ,   ,,, ,   , , , ,   , ,,,   ,,,,, , ,,,    ,,,, , ,  ,,,, ,,,,,,,,,,,,, ,,,,,,,,,,,,,
: ,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,   ,,, ,,,,,,,,, ,,, ,,,,,,, , ,   ,,,,, , ,,, , ,,,,,,, ,,,,, ,,:,:,:,:::i:::i:::::::,::::::,,,,
, ,,          ,,   ,   ,                                                                                        , , , ,    ,, ,   , ,
*/
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define LL long long
#define ll   long long
#define ull unsigned long long
#define ULL ull
#define mp make_pair
#define pii pair<int,int>
#define piii pair<int, pii >
#define pll pair <ll,ll>
#define pb push_back
#define PB pop_back
#define p push
#define P pop
#define big 20160116
#define INF 2147483647
#define ull unsigned long long
#define vi vector < int >
#define vpii vector < pii >
#define pq priority_queue
#define rep(i,n) for (int (i)=0;(i)<n;(i)++)
#define End return 0
#define mi multiset <int>
#define si set <int>
#define sll set<ll>
#define mll multiset<ll>
#define vll vector <ll>
#define Rep(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
using namespace std;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
const int Maxn=2e5+5;
int a[Maxn];
int bit[Maxn];
void Add(int x,int v){
	while (x<Maxn){
		bit[x]=max(bit[x],v);
		x+=x&-x;
	}
}
int query(int x){
	int ans=0;
	while (x){
		ans=max(ans,bit[x]);
		x-=x&-x;
	}
	return ans;
}
int pos[Maxn];
int ans[Maxn];
int main(){
	int n;
	scanf("%d",&n);
	int r=0;
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		pos[a[i]]=i;
	}
	for (int i=1;i<=n;i++){
		if (pos[i]>pos[i-1]) ans[i]=ans[i-1]+1;
		else ans[i]=1;
		r=max(r,ans[i]);
	}
	printf("%d\n",n-r);
	return 0;
}

Measured memory_bytes: 2560