B. Divan и новый проект
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Компания «Divan's Sofas» хочет построить на координатной прямой $$$n + 1$$$ различное здание так, чтобы:

  • координата каждого здания являлась целым числом;
  • никакие два здания не стоят в одной точке.

Пусть $$$x_i$$$ — координата $$$i$$$-го здания. Чтобы добраться из $$$i$$$-го здания в $$$j$$$-е, Divan будет тратить $$$|x_i - x_j|$$$ минут, где $$$|y|$$$ — модуль числа $$$y$$$.

Все здания, которые Divan построит, будут пронумерованы от $$$0$$$ до $$$n$$$. Бизнесмен будет жить в здании номер $$$0$$$ — новом главном офисе «Divan's Sofas». За первые десять лет после строительства Divan посетит $$$i$$$-е здание $$$a_i$$$ раз, каждый раз тратя $$$2 \cdot |x_0-x_i|$$$ минут на ходьбу.

Divan просит вас выбрать координаты всех $$$n + 1$$$ зданий так, чтобы за следующие десять лет бизнесмен потратил как можно меньше времени на ходьбу.

Входные данные

Каждый тест содержит несколько наборов входных данных.

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных.

Первая строка каждого набора содержит целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество зданий, которое собирается построить «Divan's Sofas», не считая главного офиса компании.

Вторая строка содержит последовательность целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^6$$$), где $$$a_i$$$ — количество посещений $$$i$$$-го здания.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных в первой строке выведите число $$$T$$$ — минимальное количество времени, которое потратит Divan на ходьбу.

Во второй строке выведите последовательность $$$x_0, x_1, \ldots, x_n$$$ из $$$n + 1$$$ целых чисел, где $$$x_i$$$ ($$$-10^6 \le x_i \le 10^6$$$) — выбранная координата для $$$i$$$-го здания. Можно показать, что в оптимальном ответе координаты всех зданий можно выбрать так, чтобы их абсолютная величина не превышала $$$10^6$$$.

Если оптимальных ответов несколько, выведите любой из них.

Пример
Входные данные
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
Примечание

Рассмотрим первый пример.

В нём Divan посетит первое здание $$$a_1 = 1$$$ раз, второе $$$a_2 = 2$$$ раз и третье $$$a_3 = 3$$$ раз. Тогда одно из выгодных расположений будет следующим:

  1. $$$x_0 = 2$$$ — координата главного офиса;
  2. $$$x_1 = 4$$$ — всего Divan потратит $$$2 \cdot |x_0-x_1| \cdot a_1 = 2 \cdot |2-4| \cdot 1 = 4$$$ минуты на посещение первого здания;
  3. $$$x_2 = 1$$$ — всего Divan потратит $$$2 \cdot |x_0-x_2| \cdot a_2 = 2 \cdot |2-1| \cdot 2 = 4$$$ минуты на посещение второго здания;
  4. $$$x_3 = 3$$$ — всего Divan потратит $$$2 \cdot |x_0-x_3| \cdot a_3 = 2 \cdot |2-3| \cdot 3 = 6$$$ минут на посещение третьего здания.

Тогда в сумме Divan потратит $$$4 + 4 + 6 = 14$$$ минут. Можно показать, что расположить здания так, чтобы бизнесмен потратил меньше времени, нельзя.

Также правильными ответами в первом примере могли быть $$$x = [1, 3, 2, 0]$$$, $$$x = [-5, -3, -6, -4]$$$ и другие.