Language: C++

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;

const int N = 10;
const int INF = 1 << 29;

struct state{
  lli num;
  int cnt;
  state(lli num=0, int cnt=0):num(num),cnt(cnt){}
};

int n;
lli pow10[11];
vector<int> v;

lli hash(const vector<int> &vec){
  lli res = 0, di = 1;
  
  for(int i=vec.size()-1;i>=0;i--){
    res += vec[i] * di;
    di *= 10;
  }

  return res;
}

lli reverse(lli num, int begin, int end){
  lli res = num;
  lli powbe = pow10[begin], powen = pow10[end];

  for(int i=0;i<(end-begin+1)/2;i++){
    res += powbe * (num / powen % 10 - num / powbe % 10);
    res += powen * (num / powbe % 10 - num / powen % 10);
    powbe *= 10;
    powen /= 10;
  }
  
  return res;
}

int bfs(lli num, map<lli, int> mp[2], int mp_pos){
  int res = INF;
  queue<state> q;
  state u, u2;

  mp[mp_pos][num] = 0;

  for(q.push(state(num, 0)); !q.empty();){
    u = q.front();
    q.pop();

    if(mp_pos == 1 && mp[0].count(u.num)) res = min(res, mp[0][u.num] + u.cnt);
    if(mp_pos == 0 && u.cnt >= 4 || u.cnt >= 5) continue;

    for(int i=0;i<n-1;i++){
      for(int j=i+1;j<n;j++){
        u2 = state(reverse(u.num, i, j), u.cnt + 1);
        if(!mp[mp_pos].count(u2.num)){
          mp[mp_pos][u2.num] = u2.cnt;
          q.push(u2);
        }
      }
    }
  }

  return res;
}

int solve(){  
  vector<int> w = v;
  map<lli, int> mp[2];

  sort(w.begin(), w.end());

  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(v[i] == w[j]) {
        v[i] = j;
        break;
      }
    }
  }

  w = v;
  sort(w.begin(), w.end());

  bfs(hash(w), mp, 0);
  return bfs(hash(v), mp, 1);
}

int main(){
  pow10[0] = 1;
  for(int i=1;i<11;i++) pow10[i] = pow10[i-1] * 10;

  while(cin >> n){
    v.clear();
    for(int i=0;i<n;i++){
      int x;
      cin >> x;
      v.push_back(x);
    }
    cout << solve() << endl;
  }
}

Compiler output:
a.cc:16:5: warning: built-in function 'pow10' declared as non-function [-Wbuiltin-declaration-mismatch]
   16 | lli pow10[11];
      |     ^~~~~
a.cc: In function 'int solve()':
a.cc:90:7: error: reference to 'hash' is ambiguous
   90 |   bfs(hash(w), mp, 0);
      |       ^~~~
In file included from /usr/include/c++/14/string_view:50,
                 from /usr/include/c++/14/bits/basic_string.h:47,
                 from /usr/include/c++/14/string:54,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52,
                 from a.cc:1:
/usr/include/c++/14/bits/functional_hash.h:59:12: note: candidates are: 'template<class _Tp> struct std::hash'
   59 |     struct hash;
      |            ^~~~
a.cc:19:5: note:                 'lli hash(const std::vector<int>&)'
   19 | lli hash(const vector<int> &vec){
      |     ^~~~
a.cc:91:14: error: reference to 'hash' is ambiguous
   91 |   return bfs(hash(v), mp, 1);
      |              ^~~~
/usr/include/c++/14/bits/functional_hash.h:59:12: note: candidates are: 'template<class _Tp> struct std::hash'
   59 |     struct hash;
      |            ^~~~
a.cc:19:5: note:                 'lli hash(const std::vector<int>&)'
   19 | lli hash(const vector<int> &vec){
      |     ^~~~