← 返回题目列表

Codeforces · 2104/B

B. 移到最后

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

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。

对于从 $$$1$$$ 到 $$$n$$$ 的每个整数 $$$k$$$,您必须执行以下操作:

  1. 选择$$$a$$$中的任意元素并将其移动到数组的右端(可以选择最后一个元素,则数组不会改变);
  2. 打印 $$$a$$$ 最后一个元素 $$$k$$$ 的总和;
  3. 将您在第一步中选择的元素移动到其原始位置(恢复原始数组 $$$a$$$)。

对于每个 $$$k$$$,您选择要移动的元素,以便打印的值是 最大可能.

计算每 $$$k$$$ 打印的值。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由两行组成:

  • 第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$);
  • 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印 $$$n$$$ 整数。如果 $$$k=i$$$,这些整数中的第 $$$i$$$ 应等于可以打印的最大值。

示例

输入
复制

4
7
13 5 10 14 8 15 13
6
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1
42
2
7 5

输出
复制

15 28 42 50 63 73 78 
1000000000 2000000000 3000000000 4000000000 5000000000 6000000000 
42 
7 12 

注意

让我们考虑语句中的第一个测试用例:

  • 当$$$k = 1$$$时,可以将第$$$6$$$移动到最后,数组变为$$$[13, 5, 10, 14, 8, 13, 15]$$$,打印的值为$$$15$$$;
  • 当$$$k = 2$$$时,可以将第$$$6$$$移动到最后,数组变为$$$[13, 5, 10, 14, 8, 13, 15]$$$,打印的值为$$$13 + 15 = 28$$$;
  • 当$$$k = 3$$$时,可以将第$$$4$$$移动到最后,数组变为$$$[13, 5, 10, 8, 15, 13, 14]$$$,打印的值为$$$15 + 13 + 14 = 42$$$;
  • 当$$$k = 4$$$时,可以将第$$$5$$$移动到最后,数组变为$$$[13, 5, 10, 14, 15, 13, 8]$$$,打印的值为$$$14 + 15 + 13 + 8 = 50$$$;
  • 当$$$k = 5$$$时,可以将$$$1$$$-st元素移动到末尾,数组变为$$$[5, 10, 14, 8, 15, 13, 13]$$$,打印的值为$$$14 + 8 + 15 + 13 + 13 = 63$$$;
  • 当$$$k = 6$$$时,可以将$$$1$$$-st元素移动到最后,数组变为$$$[5, 10, 14, 8, 15, 13, 13]$$$,打印的值为$$$10 + 14 + 8 + 15 + 13 + 13 = 73$$$;
  • 当$$$k = 7$$$时,可以将第$$$6$$$移动到末尾,数组变为$$$[13, 5, 10, 14, 8, 13, 15]$$$,打印的值为$$$13 + 5 + 10 + 14 + 8 + 13 + 15 = 78$$$。