// File Name: 3670.cpp

 // Author: Missa_Chen

 // Created Time: 2013年07月08日 星期一 21时15分34秒

 #include <iostream>

 #include <string>

 #include <algorithm>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <queue>

 #include <map>

 #include <stack>

 #include <set>

 #include <cstdlib>

 #include <vector>

 #include <time.h>

 using namespace std;

 #define LL long long

 const int inf = 0x3f3f3f3f;

 const int maxn = 3e4 + ;

 int a[maxn], dp[maxn], D[maxn], len, n;

 //dp[i]表示以第i个元素为子序列最后一个元素的LIS长度。

 //D[len]表示上升子序列长度为len的最后一个元素。

 int LIS()

 {

     len = ;

     memset(dp, , sizeof(dp));

     memset(D, , sizeof(D));

     int ret = ;

     for (int i = ; i <= n; ++i)

     {

         if (a[i] >= D[len])

         {

             dp[i] = len + ;

             D[++len] = a[i];

         }

         else

         {

             int low = , high = len, tmp = ;

             while (low <= high)

             {

                 int mid = (low + high) >> ;

                 if (D[mid] <= a[i])

                 {

                     tmp = mid;

                     low = mid + ;

                 }

                 else

                     high = mid - ;

             }

             dp[i] = tmp + ;

             D[tmp + ] = a[i];

         }

         ret = max(ret, dp[i]);

     }

     return ret;

 }

 int main()

 {

     while (~scanf("%d",&n))

     {

         for (int i = ; i <= n; ++i)

             scanf("%d", &a[i]);

         int ans = LIS();

         reverse(a + , a + n + );

         ans = max(ans, LIS());

         printf("%d\n", n - ans);

     }

     return ;

 }