题解：P11934 [CrCPC 2024] 排序

const ll N = 20, MAX = 6;
ll n, a[N], ans = MAX, goal;
map<ll, bool> vis;
map<ll, ll> mem;

ll hash1() {
	ll ret = 0;

	rep(i, 1, n) ret = ret * 10 + a[i] - 1;

	return ret;
}

void dfs(ll step) {
//	cout << "dfs:step=" << step << ",status=";
//
//	rep(i, 1, n) cout << a[i] << ' ';
//
//	endl;
//	pause;
	ll tmp = hash1();
//	cout << "tmp=" << tmp << '\n';
//	pause;

	if ((vis[tmp] and mem[tmp] <= step) or step >= ans)
		return;

//	cout << "signal!\n";
	vis[tmp] = 1;
	mem[tmp] = step;

	if (tmp == goal) {
		update(ans, step, min);
		return;
	}

	ll v11 = 0, v12 = 0;

	rep(i, 1, n - 1) {
		if (a[i] + 1 == a[i + 1])
			v11++;
		else if (a[i] > a[i + 1])
			v12++;
	}

	rep(i, 0, n) {
		rep(j, i, n) {
			rep(k, j, n) {
//				cout << "status=";
//
//				rep(i, 1, n) cout << a[i] << ' ';
//
//				endl;
//				pause;
//				cout << i << ' ' << j << ' ' << k << '\n';
//				pause;
				vector<ll> new1;
				new1.clear();

				rep(l, j + 1, k) new1.pb(a[l]);

				rep(l, 1, i) new1.pb(a[l]);

				rep(l, k + 1, n) new1.pb(a[l]);

				rep(l, i + 1, j) new1.pb(a[l]);

//				cout << "size:" << new1.size() << '\n';
//				pause;

//				for (ll l : new1)
//					cout << l << ' ';
//
//				endl;
//				pause;
				ll v21 = 0, v22 = 0;

				rep(l, 0, n - 2) {
					if (new1[l] + 1 == new1[l + 1])
						v21++;
					else if (new1[l] > new1[l + 1])
						v22++;
				}

//				cout << "v11=" << v11 << ",v12=" << v12 << ",v21=" << v21 << ",v22=" << v22 << '\n';
//				pause;

				if (v11 >= v21 or v22 > v12)
					ctn;

//				cout << "signal A\n";
				ll _a[N];
				cpy(_a, a);

				rep(i, 1, n) a[i] = new1[i - 1];

				dfs(step + 1);
				cpy(a, _a);
			}
		}
	}
}

int main() {
	cin >> n;

	rep(i, 1, n) cin >> a[i];

	rep(i, 0, n - 1) goal = goal * 10 + i;

//	cout << "goal=" << goal << '\n';
//	pause;
	dfs(0);

	cout << ans;
}