На бесконечной числовой прямой находятся \(n\) рождественных деревьев. \(i\)-е дерево растет на позиции \(x_i\). Гарантируется, что все значения \(x_i\) различны.
Каждая целочисленная точка может быть либо занята рождественским деревом, либо занята человеком, либо не занята вообще. Нецелые точки не могут быть заняты ничем.
Есть \(m\) человек, которые хотят отпраздновать Рождество. Пусть \(y_1, y_2, \dots, y_m\) — это позиции людей (заметьте, что все значения \(x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_m\) должны быть различны и все \(y_j\) должны быть целыми). Вы хотите найти такое расположение людей, что значение \(\sum\limits_{j=1}^{m}\min\limits_{i=1}^{n}|x_i - y_j|\) минимально возможное (другими словами, сумма расстояний до ближайшего рождественского дерева по всем людям должна быть минимизирована).
Другими словами, пусть \(d_j\) равно дистанции от \(j\)-го человека до ближайшего к нему рождественского дерева (\(d_j = \min\limits_{i=1}^{n} |y_j - x_i|\)). Тогда вам надо выбрать такие позиции \(y_1, y_2, \dots, y_m\), что \(\sum\limits_{j=1}^{m} d_j\) минимально возможна.
Выходные данные
В первой строке выведите одно целое число \(res\) — минимально возможное значение \(\sum\limits_{j=1}^{m}\min\limits_{i=1}^{n}|x_i - y_j|\) (другими словами, сумму расстояний до ближайшего рождественского дерева по всем людям).
Во второй строке выведите \(m\) целых чисел \(y_1, y_2, \dots, y_m\) (\(-2 \cdot 10^9 \le y_j \le 2 \cdot 10^9\)), где \(y_j\) равно позиции \(j\)-го человека. Все \(y_j\) должны быть различными, а еще все значения \(x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_m\) должны быть различными.
Если существует несколько ответов, выведите любой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 6
1 5
|
8
-1 2 6 4 0 3
|
|
2
|
3 5
0 3 1
|
7
5 -2 4 -1 2
|