CF2148G Farmer John's Last Wish

Bessie 在地上发现了一个长度为 $n$ 的数组 $a$。在数组旁边似乎还有一张手写的便签，看起来是 Farmer John 写的。便签上写着： “亲爱的 Bessie，请帮帮我！设 $f(a)$ 表示在区间 $[1, n)$ 内使得 $\gcd(a_1, a_2, \ldots, a_k) > \gcd(a_1, a_2, \ldots, a_{k+1})$ 的最大的整数 $k$，如果不存在这样的 $k$，则为 $0$。” Bessie 决定帮助 FJ。她定义 $g(a)$ 表示所有 $a$ 的重排中 $f(a)$ 的最大值。 Bessie 不仅打算找到 $g(a)$，还打算对于 $a$ 的每个前缀 $p$ 求出 $g(p)$ 的值。 输出 $n$ 个整数，第 $i$ 个数表示 $g([a_1, a_2, \ldots, a_i])$。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例组数。 每组测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）。 接下来一行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$）。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，在一行内输出 $n$ 个整数，第 $i$ 个数应为 $g([a_1, a_2, \ldots, a_i])$。

由 ChatGPT 5 翻译