← 返回题目列表

Codeforces · 2110/F

F. 教师

中文机器翻译题面 查看原题

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$$$ 的所有前缀的优点。

示例

输入
复制

2
5
3 1 4 1 5
7
5 11 11 4 2 1 10

输出
复制

0 1 4 4 5 
0 6 6 7 7 7 11 

注意

数组 $$$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$$$。