Компания «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\) — минимальное количество времени, которое потратит Divan на ходьбу.
Во второй строке выведите последовательность \(x_0, x_1, \ldots, x_n\) из \(n + 1\) целых чисел, где \(x_i\) (\(-10^6 \le x_i \le 10^6\)) — выбранная координата для \(i\)-го здания. Можно показать, что в оптимальном ответе координаты всех зданий можно выбрать так, чтобы их абсолютная величина не превышала \(10^6\).
Если оптимальных ответов несколько, выведите любой из них.
Примечание
Рассмотрим первый пример.
В нём Divan посетит первое здание \(a_1 = 1\) раз, второе \(a_2 = 2\) раз и третье \(a_3 = 3\) раз. Тогда одно из выгодных расположений будет следующим:
- \(x_0 = 2\) — координата главного офиса;
- \(x_1 = 4\) — всего Divan потратит \(2 \cdot |x_0-x_1| \cdot a_1 = 2 \cdot |2-4| \cdot 1 = 4\) минуты на посещение первого здания;
- \(x_2 = 1\) — всего Divan потратит \(2 \cdot |x_0-x_2| \cdot a_2 = 2 \cdot |2-1| \cdot 2 = 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]\) и другие.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|