有向环上 $a \to b$ 经过的最小边数被定义为单词 $a$ 和单词 $b$ 之间的语义偏差度 —— 由于翻译家并不像 OI 选手那样具备逆向思维，因此单词 $a$ 和单词 $b$ 之间的语义偏差度不一定等于单词 $b$ 和单词 $a$ 之间的语义偏差度。

考虑逆向思维，从单词 $i$ 沿着与题目描述相反的方向回译到单词 $i$。

（在下面的讨论中，我们默认单词 $i$ 可以翻译到单词 $i$ 本身，因为这显然不影响答案 —— 这只会增加翻译次数，而不能推进翻译进度，没人愿意这么做。）

于是我们惊喜地发现：

• 单词 $i$ 反向翻译一次能翻译到的单词恰好在环上构成一个半开半闭区间，其中闭区间的端点是单词 $i$ 本身，开区间的端点是距离单词 $i$ 反向距离最近的同语言单词 $j$。
• 在此基础上，如果我们再进行一次反向翻译，那么能翻译到的单词是所有「上一次能翻译到的单词」这次能翻译到的单词的并集。因为所有区间都是闭区间点为本身的半开半闭区间，所以这些区间的并集仍然是半开半闭区间，其中开区间的端点是所有「子区间内开区间的端点」中距离单词 $i$ 反向最远的单词。
• 随着翻译次数的增加，当这个反向最远的单词从单词 $i$ 开始绕着环反向跑了一圈又穿过单词 $i$ 来到它后面时，我们就求出了回译单词 $i$ 所需的最小翻译次数 —— 它就是使得这一事件发生所需的最小翻译次数。

直接二分每个答案并用 ST 表和（不属于 ST 表的）倍增实现对那个反向最远的单词的高效查询即可。

最终的时间复杂度为 $O(Tn \log^2 n)$，空间复杂度为 $O(n \log^2 n)$，瓶颈均在预处理部分。

（实际上，我们也可以套用 $O(n)-O(1)$ RMQ 把时间复杂度降到 $O(Tn \log n)$，空间复杂度降到 $O(n \log n)$，但是意义不大。）

#include <bits/stdc++.h>
using namespace std;
const int N = 2 * 1e5 + 12;
const int D = 17;
const int W = 18;
int a[N];
int b[N];
int logs[N];
int st[W][W][N];
void setst(int n, int x)
{
	for (int i = 1; i <= D; i++)
		for (int j = 1; j <= n - (1 << (i - 1)); j++)
			st[x][i][j] = min(st[x][i - 1][j + (1 << (i - 1))], st[x][i - 1][j]);
}
int getst(int l, int r, int x)
{
	int y = logs[r - l + 1];
	return min(st[x][y][l], st[x][y][r - (1 << y) + 1]);
}
int main()
{
	freopen("translation.in", "r", stdin);
	freopen("translation.out", "w", stdout);
	for (int i = 1; i <= D; i++)
		logs[1 << i] = i;
	for (int i = 3; i <= N - 1; i++)
		if (!logs[i]) logs[i] = logs[i - 1];
	int T;
	scanf("%d", &T);
	while (T--)
	{
		int n;
		scanf("%d", &n);
		int m = (n << 1);
		memset(st, 0x7f, sizeof st);
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
			a[i + n] = a[i];
			b[a[i]] = 0;
		}
		for (int i = 1; i <= m; i++)
		{
			st[0][0][i] = b[a[i]] + 1;
			b[a[i]] = i;
		}
		for (int i = 0; i <= D; i++)
			st[i][0][1] = 1;
		setst(m, 0);
		for (int i = 1; i <= D; i++)
		{
			for (int j = 2; j <= m; j++)
				st[i][0][j] = getst(st[i - 1][0][j], j, i - 1);
			setst(m, i);
		}
		for (int i = n + 1; i <= m; i++)
		{
			int ans = 1;
			int cur = i;
			for (int j = D; j >= 0; j--)
			{
				int to = getst(cur, i, j);
				if (to > i - n)
				{
					ans += (1 << j);
					cur = to;
				}
			}
			printf("%d", ans);
			if (i < m) putchar(' ');
		}
		puts("");
	}
	return 0;
}