重点单词：

coordinate n.坐标； v.协调，配合； adj.同等重要的；

line coordinate n .坐标轴；

出处：https://acs.jxnu.edu.cn/contest/24/board/challenge/D

Divan and a New Project

描述：

The company "Divan's Sofas" is planning to build n+1">n+1n+1 different buildings on a coordinate line so that:

“Divan沙发”公司计划在一条坐标线上建造n+1栋不同的建筑，并做到如下要求：

• the coordinate of each building is an integer number;
• no two buildings stand at the same point.
• 每栋建筑的坐标是一个整数；

• 没有两栋建筑站在同一个点上。

Let xi">xixi be the coordinate of the i">ii-th building. To get from the building i">ii to the building j">jj, Divan spends |xi−xj|">|xi?xj||xi?xj| minutes, where |y|">|y||y| is the absolute value of y">yy.

xi">i">i">j">|xi−xj|">|y|">y">让xi作为每一个建筑坐标的代表。为了从建筑i到建筑j，Divan花了| xi?xj |分钟，|y|是y的绝对值。

All buildings that Divan is going to build can be numbered from 0">00 to n">nn. The businessman will live in the building 0">00, the new headquarters of "Divan's Sofas". In the first ten years after construction Divan will visit the i">ii-th building ai">aiai times, each time spending 2⋅|x0−xi|">2?|x0?xi|2?|x0?xi| minutes for walking.

Divan将要建造的所有建筑都可以从0到n编号。这位商人将住在0号建筑，“Divan沙发”的新总部。在施工后的前十年里，Divan将参观ai建筑，每次花费2?|x0?xi | 步行分钟。

Divan asks you to choose the coordinates for all n+1">n+1n+1 buildings so that over the next ten years the businessman will spend as little time for walking as possible.

n+1">Divan要求您为所有n+1建筑选择坐标，以便在未来十年内，商人将尽可能少地花费时间步行。

输入：

Each test contains several test cases. The first line contains one integer number t">tt (1≤t≤103">1≤t≤1031≤t≤103) — the number of test cases.

The first line of each case contains an integer n">nn (1≤n≤2⋅105">1≤n≤2?1051≤n≤2?105) — the number of buildings that "Divan's Sofas" is going to build, apart from the headquarters.

The second line contains the sequence a1,a2,…,an">a1,a2,…,ana1,a2,…,an (0≤ai≤106">0≤ai≤1060≤ai≤106), where ai">aiai is the number of visits to the i">ii-th building.

It is guaranteed that the sum of n">nn over all test cases does not exceed 2⋅105">2?1052?105.

每个测试包含几个测试用例。第一行包含一个整数t（1≤T≤1031≤T≤103）-测试用例的数量。

每种情况的第一行包含一个整数nn（1≤N≤2.?1051≤N≤2.?105）-除总部外，“Divan’s Sofas”将建造的建筑数量。

第二行包含序列a1，a2，…，ana1，a2，…，an（0≤ai≤1060），其中ai是第二栋楼的参观次数。

保证所有测试用例的nn之和不超过2?1052?105

输出：

For each test case, on the first line print the number T">TT — the minimum time Divan will spend walking.

On the second line print the sequence x0,x1,…,xn">x0,x1,…,xnx0,x1,…,xn of n+1">n+1n+1 integers, where xi">xixi (−106≤xi≤106">?106≤xi≤106?106≤xi≤106) is the selected coordinate of the i">ii-th building. It can be shown that an optimal answer exists with coordinates not exceeding 106">106106.

If there are multiple answers, print any of them.

对于每个测试用例，在第一行打印数字T——Divan行走的最短时间。

在第二行打印n+1n+1整数的序列x0，x1，…，xnx0，x1，…，xn，其中xixi(?106≤席≤106?106≤席≤106）是第二栋建筑的选定坐标。可以证明，在坐标不超过106106的情况下，存在一个最优答案。

如果有多个答案，请打印其中任何一个。

样例输入：

4
3
1 2 3
5
3 8 10 6 1
5
1 1 1 1 1
1
0

样例输出：

14
2 4 1 3
78
1 -1 0 2 3 4
18
3 6 1 5 2 4
0
1 2

注释：

Let's look at the first example.

Divan will visit the first building a1=1">a1=1a1=1 times, the second a2=2">a2=2a2=2 times and the third a3=3">a3=3a3=3 times. Then one of the optimal solution will be as follows:

1. the headquarters is located in x0=2">x0=2x0=2;
2. x1=4">x1=4x1=4: Divan will spend 2⋅|x0−x1|⋅a1=2⋅|2−4|⋅1=4">2?|x0?x1|?a1=2?|2?4|?1=42?|x0?x1|?a1=2?|2?4|?1=4 minutes walking to the first building;
3. x2=1">x2=1x2=1: Divan will spend 2⋅|x0−x2|⋅a2=2⋅|2−1|⋅2=4">2?|x0?x2|?a2=2?|2?1|?2=42?|x0?x2|?a2=2?|2?1|?2=4 minutes walking to the second building;
4. x3=3">x3=3x3=3: Divan will spend 2⋅|x0−x3|⋅a3=2⋅|2−3|⋅3=6">2?|x0?x3|?a3=2?|2?3|?3=62?|x0?x3|?a3=2?|2?3|?3=6 minutes walking to the third building.

In total, Divan will spend 4+4+6=14">4+4+6=144+4+6=14 minutes. It can be shown that it is impossible to arrange buildings so that the businessman spends less time.

Among others, x=[1,3,2,0]">x=[1,3,2,0]x=[1,3,2,0], x=[−5,−3,−6,−4]">x=[?5,?3,?6,?4]x=[?5,?3,?6,?4] are also correct answers for the first example.

让我们来看第一个例子。

Divan将参观第一栋建筑a1=1a1=1次，第二栋建筑a2=2a2=2次，第三栋建筑a3=3a3=3次。然后，最佳解决方案之一如下所示：

总部位于x0=2x0=2；

x1=4x1=4:Divan将花费2?|x0?x1|?a1=2?|2.?4|?1=42?|x0?x1|?a1=2?|2.?4|?1=步行4分钟到第一栋建筑；

x2=1x2=1:Divan将花费2?|x0?x2|?a2=2?|2.?1|?2=42?|x0?x2|?a2=2?|2.?1|?2=步行4分钟到第二栋建筑；

x3=3x3=3:Divan将花费2?|x0?x3|?a3=2?|2.?3|?3=62?|x0?x3|?a3=2?|2.?3|?3=步行6分钟到第三栋建筑。

总的来说，Divan将花费4+4+6=144+4+6=14分钟。可以证明，不可能安排建筑物，以便商人花费更少的时间。

其中，x=[1,3,2,0]x=[1,3,2,0]，x=[?5.?3.?6.?4] x=[?5.?3.?6.?4] 这也是第一个例子的正确答案。