CF2110F Faculty

在 2077 年，世界被机器人奴役后，机器人决定实施教育改革，现在取模运算仅在"古代世界历史"学院中教授。以下是该学院的入学任务之一： 我们定义一个正整数数组 $b$ 的美观度为所有 $1 \leq i, j \leq n$ 数对中 $f(b_i, b_j)$ 的最大值，其中 $f(x, y) = (x \bmod y) + (y \bmod x)$。 给定一个长度为 $n$ 的正整数数组 $a$，输出 $n$ 个数字，其中第 $i$ 个数字（$1 \leq i \leq n$）是数组 $a_1, a_2, \ldots, a_i$ 的美观度。 $x \bmod y$ 表示 $x$ 除以 $y$ 的余数。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^6$）——数组 $a$ 的大小。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$）。 保证所有测试用例的 $n$ 之和不超过 $10^6$。

对于每个测试用例，输出 $n$ 个整数——数组 $a$ 的所有前缀的美观度。

数组 $3$ 的美观度为 $0$。 数组 $3, 1$ 的美观度为 $f(3, 1) = 1$。 数组 $3, 1, 4$ 的美观度为 $f(3, 4) = 4$。 数组 $3, 1, 4, 1$ 的美观度为 $f(4, 3) = 4$。 数组 $3, 1, 4, 1, 5$ 的美观度为 $f(4, 5) = 5$。 翻译由 DeepSeek V3 完成