← 返回题目列表

Codeforces · 2232/B

B. 蛋糕调平

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

Alice 正在为她的聚会准备蛋糕。然而,她太匆忙了,所以蛋糕上的糖霜不均匀。为了快速解决这个问题,爱丽丝会把刀放在某个地方。 整数 高度,然后从左到右扫糖霜,使糖霜水平。

正式地,令 $$$a_i$$$ 为第 $$$i$$$ 个位置处的糖霜高度。假设爱丽丝把刀放在某个地方 整数 高度 $$$h$$$。如果位置 $$$i$$$ 处的糖霜高度大于 $$$h$$$,则多余的糖霜将被推至位置 $$$i + 1$$$。 $$$n$$$ 位置上多余的糖霜将完全从蛋糕上脱落。

爱丽丝和她的朋友们真的很喜欢蛋糕糖霜。由于 Alice 可能决定提供蛋糕的某些前缀而不是整个蛋糕,因此请帮助她找到糖霜的最大高度,同时保持 $$$i = 1, 2, \ldots, n$$$ 的前 $$$i$$$ 位置的糖霜水平。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$) — 爱丽丝蛋糕的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 第 $$$i$$$ 位置处的糖霜高度。

所有测试用例的 $$$n$$$ 总和最多为 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$n$$$ 整数,其中第 $$$i$$$ 个整数表示在保持前 $$$i$$$ 位置的糖霜水平的同时糖霜可以达到的最大高度。

示例

输入
复制

5
3
4 2 3
5
2 3 4 3 2
5
3 3 3 1 1
3
913764826 346182673 764382516
8
6 7 6 7 6 7 6 7

输出
复制

4 3 3
2 2 2 2 2
3 3 3 2 2
913764826 629973749 629973749
6 6 6 6 6 6 6 6

注意

第一个测试用例的解释如下:

当 $$$i = 1$$$ 时,Alice 对数组 $$$[4]$$$ 表示的蛋糕感兴趣。由于蛋糕已经平整,糖霜的最大高度为 $$$4$$$。

当 $$$i = 2$$$ 时,Alice 对数组 $$$[4, 2]$$$ 表示的蛋糕感兴趣。如果爱丽丝将刀放在 $$$4$$$ 的高度,则生成的蛋糕将具有高度 $$$[4, 2]$$$ 的糖霜,从而使蛋糕不平整。然而,如果 Alice 把刀放在 $$$3$$$ 的高度,一个单位的糖霜就会从第一个位置被推到第二个位置,使得最终蛋糕的糖霜高度为 $$$[3, 3]$$$,即被拉平。因此,在保持水平的情况下,糖霜的最大高度为 $$$3$$$。

当 $$$i = 3$$$ 时,如果 Alice 将刀放在 $$$4$$$ 的高度,则最终的糖霜级别将为 $$$[4, 2, 3]$$$。但是,如果 Alice 将刀放在 $$$3$$$ 的高度,则最终的糖霜级别将为 $$$[3, 3, 3]$$$。因此,在保持水平的情况下,糖霜的最大高度为 $$$3$$$。