#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
template<class T>void maximize(T& a, T b){
if(a < b){
a = b;
}
}
const int lim = 8e3 + 5;
int n, p[lim];
namespace sub1{
int ans = lim, perm[10];
void work(){
for(int l = 1; l <= n; l++){
for(int r = l; r <= n; r++){
bool small = false, large = false;
for(int i = l; i <= r; i++){
if(perm[i] < min(perm[l], perm[r])){
small = true;
}
else if(perm[i] > max(perm[l], perm[r])){
large = true;
}
}
if(small && large){
return;
}
}
}
int cnt = 0;
for(int i = 1; i <= n; i++){
if(perm[i] != p[i]){
cnt++;
}
}
minimize(ans, cnt);
}
void solve(){
iota(perm + 1, perm + n + 1, 1);
do{
work();
} while(next_permutation(perm + 1, perm + n + 1));
cout << ans;
}
}
namespace sub2{
int perm[14];
bool check(){
for(int l = 1; l < n; l++){
for(int r = l + 1, mi = n, ma = 0; r <= n; r++){
minimize(mi, perm[r]);
maximize(ma, perm[r]);
if(mi < min(perm[l], perm[r]) && ma > max(perm[l], perm[r])){
return false;
}
}
}
return true;
}
void solve(){
for(int i = 1; i <= n; i++){
perm[i] = p[i];
}
if(check()){
return void(cout << 0);
}
for(int ans = 1; ans < 7; ans++){
vector<int>bit, ord(ans);
for(int mask = 1; mask < (1 << n); mask++){
if(__builtin_popcount(mask) == ans){
bit.clear();
for(int i = 0; i < n; i++){
if(mask >> i & 1){
bit.push_back(i + 1);
}
}
for(int i = 1; i <= n; i++){
perm[i] = p[i];
}
bool flag = false;
iota(ord.begin(), ord.end(), 0);
do{
for(int i = 0; i < ans; i++){
perm[bit[i]] = p[bit[ord[i]]];
}
if(check()){
flag = true;
break;
}
} while(next_permutation(ord.begin(), ord.end()));
if(flag){
return void(cout << ans);
}
}
}
}
cout << 7;
}
}
namespace sub3{
const int lim = 302;
int f[lim][lim][lim];
int dp(int l, int r, int u){
if(l > r){
return 0;
}
int& ans = f[l][r][u];
if(ans != -1){
return ans;
}
int d = u + r - l;
return ans = min({dp(l + 1, r, u) + int(p[l] != d), dp(l + 1, r, u + 1) + int(p[l] != u), dp(l, r - 1, u) + int(p[r] != d), dp(l, r - 1, u + 1) + int(p[r] != u)});
}
void solve(){
memset(f, -1, sizeof(f));
cout << dp(1, n, 1);
}
}
namespace sub4{
void solve(){
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
}
cin >> n;
for(int i = 1; i <= n; i++){
cin >> p[i];
}
if(n <= 7){
sub1::solve();
}
else if(n <= 13){
sub2::solve();
}
else if(n <= 300){
sub3::solve();
}
else{
sub4::solve();
}
}
