// Be name khode //
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int maxn5 = 8e3 + 5;
int a[maxn5], ind[maxn5];
bool rem[maxn5];
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n; cin >> n;
for(int i = 0; i < n; i++){
cin >> a[i];
a[i]--;
ind[a[i]] = i;
}
int tt = 80000;
int ans = n;
while(tt--){
int l = 0, r = n - 1;
int ptl = 0, ptr = n - 1;
int cur = 0;
memset(rem, false, sizeof rem);
for(int x = 0; x < n; x++){
if(ind[ptl] == l && !rem[l]){
ptl++;
l++;
continue;
}
if(ind[ptl] == r && !rem[r]){
ptl++;
r--;
continue;
}
if(ind[ptr] == l && !rem[l]){
ptr--;
l++;
continue;
}
if(ind[ptr] == r && !rem[r]){
ptr--;
r--;
continue;
}
int ty1 = rng() % 2, ty2 = rng() % 2;
//cout << "in " << tt << ' ' << ptl << ' ' << ptr << ' ' << l << ' ' << r << ' ' << ty1 << ' ' << ty2 << endl;
if(ty1){
if(!rem[ind[ptl]])
cur++;
rem[ind[ptl]] = true;
ptl++;
}
else{
if(!rem[ind[ptr]])
cur++;
rem[ind[ptr]] = true;
ptr--;
}
if(ty2){
if(!rem[l])
cur++;
rem[l] = true;
l++;
}
else{
if(!rem[r])
cur++;
rem[r] = true;
r--;
}
}
ans = min(ans, cur);
}
cout << ans << endl;
}
