1768D - Lucky Permutation - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD 998244353
#define INF 1e18
#define db(...) __f(#__VA_ARGS__, __VA_ARGS__);

template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << '\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');
	cout.write(names, comma - names) << " : " << arg1 << " | "; __f(comma + 1, args...);
}
void __f(const char* name, vector<int> &a) { cout << name << " : "; for (auto v : a) cout << v << " "; cout << "\n";}

void solve() {
	int n;
	cin >> n;
	vector<vector<int>> g(n + 1);
	for (int i = 1; i <= n; ++i) {
		int x; cin >> x;
		g[i].push_back(x);
		g[x].push_back(i);
	}
	vector<int> vis(n + 1), s(n + 1);
	auto dfs = [&](int src, int id, int &sz, auto && dfs) -> void{
		vis[src] = id;
		sz++;
		for (auto ch : g[src]) {
			if (!vis[ch]) {
				dfs(ch, id, sz, dfs);
			}
		}
		s[src] = sz;
	};
	int id = 1, res = 0, ans = INF;
	for (int i = 1; i <= n; ++i) if (!vis[i]) {
			int sz = 0;
			dfs(i, id++, sz, dfs);
			res += sz - 1;
		}
	for (int i = 1; i < n; ++i) {
		if (vis[i] != vis[i + 1]) ans = min(ans, res + 1);
		else ans = min(ans, res - 1);
	}
	cout << ans;
}

int32_t main()
{
	fastio();
	int t = 1;
	cin >> t;
	while (t--) {
		solve();
		cout << "\n";
	}
	return 0;
}