描述

给定一个1-N的排列A1, A2, ... AN，每次操作小Hi可以选择一个数，把它放到数组的最左边。

请计算小Hi最少进行几次操作就能使得新数组是递增排列的。

输入

第一行包含一个整数N。

第二行包含N个两两不同整数A1, A2, ... AN。(1 <= Ai <= N)

对于60%的数据 1 <= N <= 20

对于100%的数据 1 <= N <= 100000

输出

一个整数代表答案

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<iomanip>

 using namespace std;

 //1523:数组重排2

 const int maxn = 1e5 + ;

 int main()

 {

     int n, a[maxn],pos[maxn];

     int res = ;

     cin >> n;

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

     {

         cin >> a[i];

         pos[a[i]] = i;

     }

     int now = ;

     for (int i = n;i >;i--)

     {

         if (pos[i] < pos[i - ])

         {

             pos[i-] = now--;

             res++;

         }

     }

     cout << res << endl;

     return ;

 }