Untitled

#include<bits/stdc++.h>

using namespace std;

map<vector<int>,int> mp;

int rep(vector<int> &a){
  if(a.empty()){return 0;}
  if(mp.find(a)!=mp.end()){
    return mp[a];
  }
  int res=0;
  for(int i=1;i<a.size();i++){
    if(a[i-1]==i){
      vector<int> und;
      for(int j=0;j<a.size();j++){
        if(j==i-1 || j==i){continue;}
        und.push_back(a[j]);
      }
      res=max(res,rep(und)+1);
    }
  }
  mp[a]=res;
  return res;
}

int pow(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}

int greedy(vector<int> a){
  int res=0;
  while(true){
    bool fin=true;
    for(int i=((int)a.size())-1;i>=1;i--){
      if(a[i-1]==i){
        vector<int> na;
        for(int j=0;j<a.size();j++){
          if(j==i-1 || j==i){continue;}
          na.push_back(a[j]);
        }
        res++;
        a=na;
        fin=false;
        break;
      }
    }
    if(fin){break;}
  }
  return res;
}

int main(){
  std::random_device seed_gen;
  std::mt19937_64 engine(seed_gen());

  int fail=0;

  while(true){
    if(mp.size()>2e6){mp.clear();}
    int n=1+(engine()%30);
    vector<int> a(n);
    for(auto &nx : a){
      nx=rand()%n+1;
    }

    int ok=rep(a);
    int gd=greedy(a);
    if(ok!=gd){
      cout << a.size() << "\n";
      for(auto &nx : a){
        cout << nx << " ";
      }cout << "\n";
      cout << ok << " " << gd << "\n";
      fail++;
      if(fail>=5){break;}
    }
  }
  return 0;
}