There are $n$ Christmas trees on an infinite number line. The $i$-th tree grows at the position $x_i$. All $x_i$ are guaranteed to be distinct.

Each integer point can be either occupied by the Christmas tree, by the human or not occupied at all. Non-integer points cannot be occupied by anything.

There are $m$ people who want to celebrate Christmas. Let $y_1, y_2, \dots, y_m$ be the positions of people (note that all values $x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_m$ should be distinct and all $y_j$ should be integer). You want to find such an arrangement of people that the value $\sum\limits_{j=1}^{m}\min\limits_{i=1}^{n}|x_i - y_j|$ is the minimum possible (in other words, the sum of distances to the nearest Christmas tree for all people should be minimized).

In other words, let $d_j$ be the distance from the $j$-th human to the nearest Christmas tree ($d_j = \min\limits_{i=1}^{n} |y_j - x_i|$). Then you need to choose such positions $y_1, y_2, \dots, y_m$ that $\sum\limits_{j=1}^{m} d_j$ is the minimum possible.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of Christmas trees and the number of people.

The second line of the input contains $n$ integers $x_1, x_2, \dots, x_n$ ($-10^9 \le x_i \le 10^9$), where $x_i$ is the position of the $i$-th Christmas tree. It is guaranteed that all $x_i$ are distinct.


-----Output-----

In the first line print one integer $res$ — the minimum possible value of $\sum\limits_{j=1}^{m}\min\limits_{i=1}^{n}|x_i - y_j|$ (in other words, the sum of distances to the nearest Christmas tree for all people).

In the second line print $m$ integers $y_1, y_2, \dots, y_m$ ($-2 \cdot 10^9 \le y_j \le 2 \cdot 10^9$), where $y_j$ is the position of the $j$-th human. All $y_j$ should be distinct and all values $x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_m$ should be distinct.

If there are multiple answers, print any of them.


-----Examples-----
Input
2 6
1 5

Output
8
-1 2 6 4 0 3 

Input
3 5
0 3 1

Output
7
5 -2 4 -1 2

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms

Graph algorithms

Shortest paths
Skill types: Greedy algorithms

Starter code:

Solutions:
from collections import deque
(n, m) = map(int, input().split())
trees = [int(i) for i in input().split()]
dist = {i: 0 for i in trees}
q = deque()
for cur in trees:
	q.append(cur)
ans_len = 0
ans_people = []
while len(q) > 0 and len(ans_people) != m:
	cur = q.popleft()
	if cur in dist and dist[cur] != 0:
		ans_len += dist[cur]
		ans_people.append(cur)
	if not cur - 1 in dist:
		dist[cur - 1] = dist[cur] + 1
		q.append(cur - 1)
	if not cur + 1 in dist:
		dist[cur + 1] = dist[cur] + 1
		q.append(cur + 1)
print(ans_len)
ans_people.sort()
for cur in ans_people:
	print(cur, end=' ')


import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict
from heapq import *

class Data:

	def __init__(self, x, y, val, type):
		self.x = x
		self.y = y
		self.val = val
		self.type = type

	def v(self):
		return (self.x, self.y, self.val, self.type)

	def __lt__(self, other):
		return self.val < other.val

def main():
	(n, m) = map(int, input().split())
	a = sorted(map(int, input().split()))
	b = []
	heapify(b)
	for i in range(n - 1):
		if a[i + 1] - a[i] > 1:
			heappush(b, Data(a[i], a[i + 1], 1, 'R'))
	heappush(b, Data(a[0], -2 * 10 ** 10 - 1, 1, 'a'))
	heappush(b, Data(a[-1], 2 * 10 ** 10 + 1, 1, 'b'))
	z = 0
	ans = 0
	c = []
	while z != m:
		d = heappop(b)
		ans += d.val
		if abs(d.y - d.x) != 2:
			u = d.type
			if u == 'R':
				c.append(d.x + 1)
				heappush(b, Data(d.x + 1, d.y, d.val, 'L'))
			elif u == 'L':
				c.append(d.y - 1)
				heappush(b, Data(d.x, d.y - 1, d.val + 1, 'R'))
			elif u == 'a':
				c.append(d.x - 1)
				heappush(b, Data(d.x - 1, d.y, d.val + 1, 'a'))
			elif u == 'b':
				c.append(d.x + 1)
				heappush(b, Data(d.x + 1, d.y, d.val + 1, 'b'))
		else:
			c.append(d.x + 1)
		z += 1
	print(ans)
	print(*c)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from collections import deque
(n, m) = list(map(int, input().split()))
x = list(map(int, input().split()))
dic = {}
q = deque([])
d = 0
ans = []
for i in range(n):
	dic[x[i]] = 1
for i in range(n):
	if x[i] - 1 not in dic:
		dic[x[i] - 1] = 1
		q.append([x[i] - 1, 1, 'l'])
	if x[i] + 1 not in dic:
		dic[x[i] + 1] = 1
		q.append([x[i] + 1, 1, 'r'])
for i in range(m):
	now = q.popleft()
	p = now[0]
	d += now[1]
	direc = now[2]
	ans.append(p)
	if direc == 'l':
		if p - 1 not in dic:
			dic[p - 1] = 1
			q.append([p - 1, now[1] + 1, direc])
	elif p + 1 not in dic:
		dic[p + 1] = 1
		q.append([p + 1, now[1] + 1, direc])
print(d)
print(' '.join(map(str, ans)))


(po, men) = map(int, input().split())
a = {int(i) for i in input().split()}
f = {*a}
r = set()
k = 1
s = 0
while len(r) < men:
	b = set()
	for i in a:
		for p in (-1, 1):
			if i + p * k not in f:
				if len(r) < men:
					s += abs(p * k)
					r.add(i + p * k)
					f.add(i + p * k)
					b.add(i)
					if len(r) == men:
						break
		if len(r) == men:
			break
	k += 1
	a = {*b}
print(s)
print(*r)


import heapq
(n, m) = map(int, input().split())
x = [int(o) for o in input().split()]
c = 0
i = 1
j = 1
k = 0
s = set(x)
h = []
ans = []
for i in range(n):
	if x[i] - 1 not in s:
		heapq.heappush(h, [1, -1, x[i] - 1])
	if x[i] + 1 not in s:
		heapq.heappush(h, [1, 1, x[i] + 1])
while c != m:
	lol = heapq.heappop(h)
	if lol[1] > 0:
		if lol[2] not in s:
			s.add(lol[2])
			ans.append(lol[2])
			c += 1
			k += lol[0]
			lol[1] += 1
			lol[0] += 1
			lol[2] += 1
			if lol[2] not in s:
				heapq.heappush(h, lol[:])
	elif lol[2] not in s:
		s.add(lol[2])
		ans.append(lol[2])
		c += 1
		k += lol[0]
		lol[1] -= 1
		lol[0] += 1
		lol[2] -= 1
		if lol[2] not in s:
			heapq.heappush(h, lol[:])
print(k)
print(*ans)


import sys
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
X = list(map(int, input().split()))
SET = set(X)
dis = 1
ANS = []
MSET = set(X)
PSET = set(X)
score = 0
MEM = 0
while MEM < m:
	REMLIST = []
	for t in MSET:
		if t - dis in SET:
			REMLIST.append(t)
		else:
			ANS.append(t - dis)
			SET.add(t - dis)
			MEM += 1
			score += dis
		if MEM == m:
			break
	MSET -= set(REMLIST)
	if MEM == m:
		break
	REMLIST = []
	for t in PSET:
		if t + dis in SET:
			REMLIST.append(t)
		else:
			ANS.append(t + dis)
			SET.add(t + dis)
			MEM += 1
			score += dis
		if MEM == m:
			break
	PSET -= set(REMLIST)
	dis += 1
print(score)
print(*ANS)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
d = {}
a.sort()
low = 1
high = m
for i in a:
	d[i] = 2
from collections import deque

def check(mid, a):
	s = 0
	for i in range(n - 1):
		s += min(2 * mid, a[i + 1] - a[i] - 1)
	if s + 2 * mid >= m:
		return True
	else:
		return False
while low < high:
	mid = (low + high) // 2
	if check(mid, a):
		high = mid
	else:
		low = mid + 1
st = deque(a)
k = 0
ans = []
pr = 0
while m > 0:
	if st[0] == a[0]:
		k += 1
	if st[0] - k in d and st[0] + k in d:
		st.popleft()
		continue
	if st[0] - k not in d:
		d[st[0] - k] = 1
		m -= 1
		pr += k
		ans.append(st[0] - k)
	if st[0] + k not in d and m > 0:
		d[st[0] + k] = 1
		m -= 1
		pr += k
		ans.append(st[0] + k)
	st.append(st.popleft())
print(pr)
print(*ans)


(n, y) = map(int, input().split())
q = list(map(int, input().split()))
(v, m, ans, j) = ([], {}, 0, 0)
for i in q:
	m[i] = 0
while len(v) != y:
	x = q[j]
	if m[x]:
		ans += m[x]
		v.append(x)
	if x + 1 not in m:
		m[x + 1] = m[x] + 1
		q.append(x + 1)
	if x - 1 not in m:
		m[x - 1] = m[x] + 1
		q.append(x - 1)
	j += 1
print(ans, '\n', *v)


import heapq
(n, m) = map(int, input().split())
x = list(map(int, input().split()))
y = []
total_distance = 0
occupied = set(x)
Q = [(1, tree + d) for tree in x for d in (1, -1)]
while len(y) < m:
	(distance, position) = heapq.heappop(Q)
	if position not in occupied:
		y.append(position)
		total_distance += distance
		occupied.add(position)
		heapq.heappush(Q, (distance + 1, position + 1))
		heapq.heappush(Q, (distance + 1, position - 1))
print(total_distance)
print(*y)


import sys, collections
(N, M) = [int(i) for i in sys.stdin.readline().strip().split(' ')]
T = [int(i) for i in sys.stdin.readline().strip().split(' ')]
V = set(T)
Q = collections.deque()
for t in T:
	Q.append((t - 1, 1))
	Q.append((t + 1, 1))
Y = set()
md = 0
while Q:
	(p, d) = Q.popleft()
	if p in V:
		continue
	V.add(p)
	Y.add(p)
	md += d
	if len(Y) == M:
		break
	Q.append((p + 1, d + 1))
	Q.append((p - 1, d + 1))
print(md)
print(' '.join([str(i) for i in Y]))


import heapq
import sys
from collections import deque
input = sys.stdin.readline
(n, m) = list(map(int, input().split()))
y = list(map(int, input().split()))
done = set(y)
y.sort()
a = deque([])
total = 0
for i in range(n):
	a.append((0, y[i], 'l'))
	a.append((0, y[i], 'r'))
count = 0
ans = []
while count < m:
	(val, ind, dir) = a.popleft()
	if dir == 'l':
		if ind - 1 in done:
			continue
		val += 1
		total += val
		a.append((val, ind - 1, 'l'))
		done.add(ind - 1)
		ans.append(str(ind - 1))
		count += 1
	else:
		if ind + 1 in done:
			continue
		val += 1
		total += val
		a.append((val, ind + 1, 'r'))
		done.add(ind + 1)
		ans.append(str(ind + 1))
		count += 1
print(total)
sys.stdout.write(' '.join(ans))


import sys

def ip():
	ans = 0
	(n, m) = map(int, input().split())
	x = list(map(int, input().split()))
	q = []
	d = {}
	person = []
	for i in x:
		d[i] = 0
		q.append(i)
	ptr = 0
	while q:
		if len(person) == m:
			break
		rmv = q[ptr]
		ptr += 1
		if d[rmv] != 0:
			person.append(rmv)
			ans += d[rmv]
		if d.get(rmv - 1) == None:
			d[rmv - 1] = d[rmv] + 1
			q.append(rmv - 1)
		if d.get(rmv + 1) == None:
			d[rmv + 1] = d[rmv] + 1
			q.append(rmv + 1)
	print(ans)
	person = sorted(person)
	print(*person)
ip()


from collections import defaultdict
value = input().strip().split()
(n, m1) = (int(value[0]), int(value[1]))
a = [int(i) for i in input().strip().split()]
m = defaultdict(bool)
q = list()
for i in a:
	m[i] = 0
	q.append(i)
ans = 0
res = []
y = 0
while len(q) != 0:
	x = q[y]
	if len(res) == m1:
		break
	if m[x] != 0:
		ans += m[x]
		res.append(x)
	if m[x - 1] is False:
		m[x - 1] = m[x] + 1
		q.append(x - 1)
	if m[x + 1] is False:
		m[x + 1] = m[x] + 1
		q.append(x + 1)
	y += 1
print(ans)
for i in res:
	print(i, end=' ')


(n, m) = map(int, input().split())
arr = sorted(list(map(int, input().split())))
(que, vis) = ([], {})
for i in arr:
	que.append((i, 1))
	vis[i] = 1

def bfs():
	(tot_sum, res) = (0, [])
	(p1, p2) = (0, len(que) - 1)
	while p1 <= p2:
		(x, y) = que[p1]
		p1 += 1
		if x + 1 not in vis:
			vis[x + 1] = 1
			que.append((x + 1, y + 1))
			p2 += 1
			tot_sum += y
			res.append(x + 1)
		if len(res) == m:
			break
		if x - 1 not in vis:
			vis[x - 1] = 1
			que.append((x - 1, y + 1))
			p2 += 1
			tot_sum += y
			res.append(x - 1)
		if len(res) == m:
			break
	return (tot_sum, res)
(tot_sum, res) = bfs()
print(tot_sum)
print(*res)


ints = list(map(int, input().split()))
(n, m) = (ints[0], ints[1])
trees = list(map(int, input().split()))
trees.sort()
occupied = {}
for i in range(len(trees)):
	occupied[trees[i]] = 1
trees = set(trees)
overall = 0
distance = 1
guys = []
while m > 0:
	deletable = set()
	for tree in trees:
		if m == 0:
			break
		left = tree - distance
		must_delete = 0
		if left not in occupied:
			occupied[left] = 1
			guys.append(left)
			overall += distance
			m -= 1
		else:
			must_delete += 1
		if m == 0:
			break
		right = tree + distance
		if right not in occupied:
			occupied[right] = 1
			guys.append(right)
			overall += distance
			m -= 1
		else:
			must_delete += 1
		if must_delete == 2:
			deletable.add(tree)
	trees = trees - deletable
	distance += 1
print(overall)
print(*guys)


(n, m) = map(int, input().split())
trees = set(list(map(int, input().split())))
vis = set(trees)
res = []
dist = 0
for d in range(1, m + 1):
	done = False
	removal = set()
	for t in trees:
		if t - d in vis and t + d in vis:
			removal.add(t)
		if not t - d in vis:
			vis.add(t - d)
			res.append(t - d)
			dist += d
		if len(res) == m:
			done = True
			break
		if not t + d in vis:
			vis.add(t + d)
			res.append(t + d)
			dist += d
		if len(res) == m:
			done = True
			break
	if done:
		break
	for t in removal:
		trees.remove(t)
print(dist)
print(' '.join(map(str, sorted(res))))


import sys

def binsearch(val, mas):
	left = -1
	right = len(mas) - 1
	while right > left + 1:
		mid = (right + left) // 2
		if mas[mid] < val:
			left = mid
		else:
			right = mid
	try:
		return min(abs(mas[left] - val), abs(mas[right] - val))
	except IndexError:
		return abs(mas[right] - val)
(n, m) = map(int, input().split())
x = [int(i) for i in sys.stdin.readline().split()]
isx = x.copy()
isx.sort()
sx = set(x)
sum = 0
a = []
while len(a) < m:
	for i in x:
		if i + 1 not in sx:
			a.append((binsearch(i + 1, isx), i + 1))
			sum += a[len(a) - 1][0]
			sx.add(i + 1)
			x.append(i + 1)
		if len(a) == m:
			break
		if i - 1 not in sx:
			a.append((binsearch(i - 1, isx), i - 1))
			sx.add(i - 1)
			sum += a[len(a) - 1][0]
			x.append(i - 1)
		if len(a) == m:
			break
print(sum)
for i in range(m):
	sys.stdout.write(str(a[i][1]) + ' ')


import heapq, bisect

def main():
	(n, m) = map(int, input().split())
	trees = list(map(int, input().split()))
	trees.sort()
	ans = []
	distance = 0
	heap = []
	visited = set()
	for i in trees:
		visited.add(i)
	for i in trees:
		if i + 1 not in visited:
			heapq.heappush(heap, (1, i + 1))
		if i - 1 not in visited:
			heapq.heappush(heap, (1, i - 1))
	while heap:
		curr = heapq.heappop(heap)
		if curr[1] not in visited:
			distance += curr[0]
			ans.append(curr[1])
			visited.add(curr[1])
			if len(ans) == m:
				break
			if curr[1] + 1 not in visited:
				index = bisect.bisect(trees, curr[1] + 1)
				min_dist = float('inf')
				if index < len(trees):
					min_dist = min(min_dist, trees[index] - curr[1] - 1)
				if index - 1 >= 0:
					min_dist = min(min_dist, curr[1] + 1 - trees[index - 1])
				heapq.heappush(heap, (min_dist, curr[1] + 1))
			if curr[1] - 1 not in visited:
				index = bisect.bisect(trees, curr[1] - 1)
				min_dist = float('inf')
				if index < len(trees):
					min_dist = min(min_dist, trees[index] - curr[1] + 1)
				if index - 1 >= 0:
					min_dist = min(min_dist, curr[1] - 1 - trees[index - 1])
				heapq.heappush(heap, (min_dist, curr[1] - 1))
	print(distance)
	for i in ans:
		print(i, end=' ')
main()


from collections import deque
(n, m) = map(int, input().split())
x = list(map(int, input().split()))
assert len(x) == n
dist = {}
q = deque()
for e in x:
	q.append(e)
	dist[e] = 0
res = []
total = 0
while q and len(res) < m:
	u = q.popleft()
	if dist[u] > 0:
		total += dist[u]
		res.append(u)
	for d in range(-1, 2, 2):
		v = u + d
		if v not in dist:
			dist[v] = dist[u] + 1
			q.append(v)
print(total)
print(*res)


(N, K) = map(int, input().split())
L = list(map(int, input().split()))
D = {}
X = []
for i in L:
	D[i] = 1
	X.append(i)
ans = []
v = 0
i = 0
while len(ans) < K:
	x = X[i]
	if x - 1 not in D:
		v += D[x]
		ans.append(x - 1)
		X.append(x - 1)
		D[x - 1] = D[x] + 1
	if len(ans) == K:
		break
	if x + 1 not in D:
		v += D[x]
		ans.append(x + 1)
		X.append(x + 1)
		D[x + 1] = D[x] + 1
	i += 1
print(v)
print(*ans)


(n, y) = map(int, input().split(' '))
x = list(map(int, input().split(' ')))
d = {}
for i in x:
	d[i] = 0
ans = []
ind = 0
f_ans = 0
while len(ans) != y:
	if d[x[ind]]:
		f_ans += d[x[ind]]
		ans.append(x[ind])
	if x[ind] + 1 not in d:
		d[x[ind] + 1] = d[x[ind]] + 1
		x.append(x[ind] + 1)
	if x[ind] - 1 not in d:
		d[x[ind] - 1] = d[x[ind]] + 1
		x.append(x[ind] - 1)
	ind += 1
print(f_ans)
print(*ans)


def main():
	(n, m) = map(int, input().split())
	xx = set((int(a) for a in input().split()))
	xxu = xx.copy()
	xxd = xx.copy()
	yy = set()
	d = 1
	td = 0
	up = set()
	down = set()
	while m > 0:
		if xxu:
			x = xxu.pop()
			if x + 1 in xxd:
				xxd.remove(x + 1)
			else:
				yy.add(x + 1)
				up.add(x + 1)
				td += d
				m -= 1
		elif xxd:
			x = xxd.pop()
			if x - 1 in up:
				up.remove(x - 1)
			elif d > 1 or x - 1 not in xx:
				yy.add(x - 1)
				down.add(x - 1)
				td += d
				m -= 1
		else:
			d += 1
			xxu = up
			xxd = down
			up = set()
			down = set()
	print(td)
	print(' '.join(map(str, yy)))
main()


from collections import deque as dq
(n, m) = map(int, input().split())
a = sorted(list(map(int, input().split())))
s = set(a)
k = dq([])
for i in a:
	k.append((i, 0, 1, 1))
ans = 0
t = []
while m > 0:
	(p, d, l, r) = k.popleft()
	if l and p - (d + 1) not in s:
		s.add(p - (d + 1))
		t.append(p - (d + 1))
		ans += d + 1
		m -= 1
	else:
		l = 0
	if m > 0 and r and (p + (d + 1) not in s):
		s.add(p + (d + 1))
		t.append(p + (d + 1))
		ans += d + 1
		m -= 1
	else:
		r = 0
	if l or r:
		k.append((p, d + 1, l, r))
print(ans)
print(*sorted(t))


import sys
LI = lambda : list(map(int, sys.stdin.readline().strip('\n').split()))
MI = lambda : map(int, sys.stdin.readline().strip('\n').split())
SI = lambda : sys.stdin.readline().strip('\n')
II = lambda : int(sys.stdin.readline().strip('\n'))
(n, m) = MI()
a = sorted(LI())
taken = set(a)
q = a.copy()
(i, cnt) = (0, 0)
while cnt < m:
	u = q[i]
	if u - 1 not in taken:
		taken.add(u - 1)
		q.append(u - 1)
		cnt += 1
	if cnt >= m:
		break
	if u + 1 not in taken:
		taken.add(u + 1)
		q.append(u + 1)
		cnt += 1
	i += 1
ans = taken.difference(set(a))
val = 0
for v in ans:
	(l, r) = (0, n - 1)
	(v1, v2) = (-1, -1)
	while l <= r:
		m = (l + r) // 2
		if a[m] <= v:
			v1 = m
			l = m + 1
		else:
			r = m - 1
	(l, r) = (0, n - 1)
	while l <= r:
		m = (l + r) // 2
		if a[m] < v:
			l = m + 1
		else:
			v2 = m
			r = m - 1
	if v1 != -1 and v2 != -1:
		val += min(abs(v - a[v1]), abs(v - a[v2]))
	elif v1 != -1:
		val += abs(v - a[v1])
	else:
		val += abs(v - a[v2])
print(val)
print(*ans)


import sys
input = sys.stdin.readline
from collections import *

def bfs():
	q = deque(x)
	dist = defaultdict(int)
	d_sum = 0
	l = []
	for xi in x:
		dist[xi] = 0
	while q:
		v = q.popleft()
		for nv in [v - 1, v + 1]:
			if nv not in s:
				dist[nv] = dist[v] + 1
				d_sum += dist[nv]
				q.append(nv)
				s.add(nv)
				l.append(nv)
				if len(l) == m:
					return (d_sum, l)
(n, m) = map(int, input().split())
x = list(map(int, input().split()))
s = set(x)
(ans0, ans1) = bfs()
print(ans0)
print(*ans1)


(n, m) = map(int, input().split())
trees = list(map(int, input().split()))
from collections import deque
q = deque()
for t in trees:
	q.append((t, 1))
	q.append((t, -1))
cost = 0
people = []
occupied = set(trees)
while q:
	(pos, d) = q.popleft()
	if pos + d in occupied:
		continue
	people.append(pos + d)
	occupied.add(pos + d)
	cost += abs(d)
	if len(people) == m:
		break
	q.append((pos, d + 1 if d > 0 else d - 1))
print(cost)
print(*people)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import bisect
import math
(n, m) = map(int, input().split())
trees = list(map(int, input().split()))
trees.sort()
gaps = []
for s in range(1, len(trees)):
	gap = trees[s] - 1 - trees[s - 1]
	if gap > 0:
		treepos = (trees[s - 1], trees[s])
		gaps.append((gap, treepos))
gaps.sort(key=lambda x: x[0])
gaps.reverse()
gapsonly = [k[0] for k in gaps]
outy = []
res = 0
ppl = 0
cv = 1
while ppl < m:
	if ppl + 2 <= m:
		ppl += 2
		res += 2 * cv
		outy.append(trees[0] - cv)
		outy.append(trees[-1] + cv)
		for s in range(len(gaps)):
			if ppl < m:
				ppl += 1
				res += cv
				treepos = gaps[-1 - s][1]
				outy.append(treepos[0] + cv)
			else:
				break
		while len(gapsonly) >= 1 and gapsonly[-1] == 2 * cv - 1:
			gapsonly.pop()
			gaps.pop()
		for s in range(len(gaps)):
			if ppl < m:
				ppl += 1
				res += cv
				treepos = gaps[-1 - s][1]
				outy.append(treepos[1] - cv)
			else:
				break
		while len(gapsonly) >= 1 and gapsonly[-1] == 2 * cv:
			gapsonly.pop()
			gaps.pop()
	else:
		ppl += 1
		res += cv
		outy.append(trees[0] - cv)
	cv += 1
print(res)
outy = [str(k) for k in outy]
print(' '.join(outy))


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
mp = {}
q = []
for i in a:
	q.append(i)
	mp[i] = 0
(ans, res, i) = ([], 0, 0)
while len(ans) < m:
	x = q[i]
	for k in [-1, 1]:
		if x + k not in mp:
			mp[x + k] = mp[x] + 1
			res += mp[x + k]
			q.append(x + k)
			ans.append(x + k)
		if len(ans) == m:
			break
	i += 1
print(res)
print(*ans)


import sys
from heapq import heappush, heappop
(n, m, *x) = map(int, sys.stdin.read().split())
x.sort()

def main():
	filled = set(x)
	dist = []
	for v in x:
		if not v - 1 in filled:
			heappush(dist, (1, v, 'l'))
		if not v + 1 in filled:
			heappush(dist, (1, v, 'r'))
	res = []
	total = 0
	cnt = 0
	while cnt < m:
		(d, v, lr) = heappop(dist)
		if lr == 'l':
			u = v - d
		else:
			u = v + d
		if not u in filled:
			total += d
			res.append(u)
			filled.add(u)
			cnt += 1
			if lr == 'l':
				if not u - 1 in filled:
					heappush(dist, (d + 1, v, 'l'))
			elif not u + 1 in filled:
				heappush(dist, (d + 1, v, 'r'))
	print(total)
	return res
ans = main()
print(*ans, sep=' ')


(p, m) = map(int, input().split())
a = {*map(int, input().split())}
r = {*a}
z = {*a}
m += len(r)
k = 1
s = 0
while len(r) < m:
	b = set()
	for i in a:
		for p in (-1, 1):
			if i + p * k not in r:
				if len(r) < m:
					s += abs(p * k)
					r.add(i + p * k)
					b.add(i)
					if len(r) == m:
						print(s)
						print(*r - z)
						exit()
	k += 1
	a = b


(n, m) = map(int, input().split())
X = list(map(int, input().split()))
X.sort()
used = set(X)
from collections import deque
q = deque([])
for x in X:
	q.append((x, 0))
Y = set()
ans = 0
while True:
	(v, d) = q.popleft()
	if v - 1 not in used:
		Y.add(v - 1)
		used.add(v - 1)
		q.append((v - 1, d + 1))
		ans += d + 1
	if len(Y) == m:
		break
	if v + 1 not in used:
		Y.add(v + 1)
		used.add(v + 1)
		q.append((v + 1, d + 1))
		ans += d + 1
	if len(Y) == m:
		break
print(ans)
print(*Y)


from collections import deque
qu = deque([])
(n, m) = map(int, input().split())
dist = {}
ls = list(map(int, input().split()))
for i in ls:
	dist[i] = 0
	qu.append(i)
res = []
flag = True
while flag:
	x = qu.popleft()
	for dx in [-1, 1]:
		nx = x + dx
		if nx in dist:
			continue
		dist[nx] = dist[x] + 1
		qu.append(nx)
		res.append(nx)
		if len(res) == m:
			flag = False
			break
ans = sum(dist.values())
print(ans)
print(' '.join(map(str, res)))


import sys
LI = lambda : list(map(int, sys.stdin.readline().strip('\n').split()))
MI = lambda : map(int, sys.stdin.readline().strip('\n').split())
SI = lambda : sys.stdin.readline().strip('\n')
II = lambda : int(sys.stdin.readline().strip('\n'))
(n, m) = MI()
q = LI()
d = {v: 1 for v in q}
ans = []
(i, cnt, dist) = (0, 0, 0)
while cnt < m:
	u = q[i]
	if d.get(u - 1, 0) == 0:
		ans.append(u - 1)
		d[u - 1] = d[u] + 1
		cnt += 1
		dist += d[u - 1] - 1
		q.append(u - 1)
	if cnt >= m:
		break
	if d.get(u + 1, 0) == 0:
		ans.append(u + 1)
		d[u + 1] = d[u] + 1
		cnt += 1
		dist += d[u + 1] - 1
		q.append(u + 1)
	i += 1
print(dist)
print(*ans)


from collections import defaultdict
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
d1 = defaultdict(lambda : 'safal')
d2 = []
result = []
ans = 0
for i in range(n):
	d1[l[i]] = 0
	d2.append(l[i])
t = 0
while len(d2) != t:
	if len(result) == m:
		break
	cur = d2[t]
	t += 1
	if d1[cur] != 0 and d1[cur] != 'safal':
		ans += d1[cur]
		result.append(cur)
	if d1[cur - 1] == 'safal':
		d1[cur - 1] = d1[cur] + 1
		d2.append(cur - 1)
	if d1[cur + 1] == 'safal':
		d1[cur + 1] = d1[cur] + 1
		d2.append(cur + 1)
print(ans)
for i in result:
	print(i, end=' ')


(n, p) = list(map(int, input().split()))
l = list(map(int, input().split()))
trees_p = set(l)
trees_l = set(l)
zaj = {}
for i in l:
	zaj[i] = 1
dupa = 0
odp = []
odl = 0
import sys
while True:
	odl += 1
	to_rem = []
	for t in trees_l:
		try:
			zaj[t - odl]
			to_rem.append(t)
		except Exception:
			zaj[t - odl] = 1
			odp.append(t - odl)
			dupa += odl
			if len(odp) == p:
				print(dupa)
				print(*odp)
				return
	for x in to_rem:
		trees_l.remove(x)
	to_rem = []
	for t in trees_p:
		try:
			zaj[t + odl]
			to_rem.append(t)
		except Exception:
			zaj[t + odl] = 1
			odp.append(t + odl)
			dupa += odl
			if len(odp) == p:
				print(dupa)
				print(*odp)
				return
	for x in to_rem:
		trees_p.remove(x)


import sys
from collections import deque
(n, m) = map(int, sys.stdin.readline().split())
tree = list(map(int, sys.stdin.readline().split()))
visit = set(tree)
list_res = [0] * m
list_queue = deque()
for i in tree:
	list_queue.append((i, 0))
res = 0
while list_queue and m > 0:
	(now_i, now_d) = list_queue.popleft()
	for i in (1, -1):
		next_i = now_i + i
		if not next_i in visit:
			list_queue.append((next_i, now_d + 1))
			visit.add(next_i)
			res += now_d + 1
			m -= 1
			list_res[m] = next_i
			if not m:
				break
print(res)
print(*list_res)


import sys
from collections import deque
input = sys.stdin.readline
(n, m) = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
q = deque(x)
used = set(x)
ans = set()
cnt = 0
while cnt < m:
	i = q.popleft()
	if i not in used:
		used.add(i)
		ans.add(i)
		cnt += 1
	if i + 1 not in used:
		q.append(i + 1)
	if i - 1 not in used:
		q.append(i - 1)
i = 0
ans = sorted(list(ans))
dist = 0
for y in ans:
	while i + 1 < n and abs(x[i + 1] - y) < abs(x[i] - y):
		i += 1
	dist += abs(x[i] - y)
print(dist)
print(*ans)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
d = {}
v = []
for c in a:
	d[c] = 1
	v.append(c)
ans = []
dist = 0
i = 0
while len(ans) < m:
	x = v[i]
	if x - 1 not in d:
		dist += d[x]
		ans.append(x - 1)
		v.append(x - 1)
		d[x - 1] = d[x] + 1
	if len(ans) == m:
		break
	if x + 1 not in d:
		dist += d[x]
		ans.append(x + 1)
		v.append(x + 1)
		d[x + 1] = d[x] + 1
	i += 1
print(dist)
for c in ans:
	print(c, end=' ')


import heapq
(n, m) = map(int, input().split())
x = sorted(map(int, input().split()))
pos = [(1, x[0] - 1, -1, m), (1, x[-1] + 1, 1, m)]
for i in range(n - 1):
	left = (x[i + 1] - x[i]) // 2
	right = (x[i + 1] - x[i] - 1) // 2
	if left:
		pos.append((1, x[i] + 1, 1, left))
	if right:
		pos.append((1, x[i + 1] - 1, -1, right))
answer = []
total = 0
for i in range(m):
	(dist, xx, direction, maxval) = heapq.heappop(pos)
	answer.append(xx)
	total += dist
	if dist < maxval:
		heapq.heappush(pos, (dist + 1, xx + direction, direction, maxval))
print(total)
print(' '.join(map(str, answer)))


from collections import defaultdict as dc
from heapq import *
import math
import bisect
from collections import deque as dq
(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
p = dc(int)
cnt = dc(int)
q = dq([])
ans = []
d = 0
for i in range(n):
	p[a[i]] = 0
	q.append(a[i])
	cnt[a[i]] = 1
while len(q):
	if len(ans) == m:
		break
	k = q.popleft()
	if p[k] != 0:
		d += p[k]
		ans.append(k)
	if cnt[k - 1] == 0:
		p[k - 1] = p[k] + 1
		q.append(k - 1)
		cnt[k - 1] = 1
	if cnt[k + 1] == 0:
		p[k + 1] = p[k] + 1
		q.append(k + 1)
		cnt[k + 1] = 1
print(d)
print(*ans)


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def solve():
	(n, m) = mints()
	q = list(mints())
	w = dict()
	for i in q:
		w[i] = 0
	ql = 0
	c = 0
	ss = 0
	y = []
	while ql < len(q):
		p = q[ql]
		ql += 1
		x = p - 1
		if x not in w:
			d = w[p] + 1
			y.append(x)
			q.append(x)
			ss += d
			w[x] = d
			c += 1
			if c == m:
				break
		x = p + 1
		if x not in w:
			d = w[p] + 1
			q.append(x)
			y.append(x)
			ss += d
			w[x] = d
			c += 1
			if c == m:
				break
	print(ss)
	print(' '.join(map(str, y)))
solve()


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
trees = [int(i) for i in input().split()]
people = {}
for i in range(n):
	people[trees[i]] = 0
dist = 0
i = 0
while m > 0:
	last = trees[i]
	if last - 1 not in people:
		people[last - 1] = people[last] + 1
		m -= 1
		trees.append(last - 1)
		dist += people[last - 1]
		if m == 0:
			break
	if last + 1 not in people:
		people[last + 1] = people[last] + 1
		m -= 1
		trees.append(last + 1)
		dist += people[last + 1]
		if m == 0:
			break
	i += 1
print(dist)
print(*trees[n:])


from collections import defaultdict
(n, m1) = map(int, input().strip().split())
a = map(int, input().strip().split())
m = {}
q = list()
for i in a:
	m[i] = 0
	q.append(i)
ans = 0
res = []
j = 0
while len(res) != m1:
	x = q[j]
	if m[x] != 0:
		ans += m[x]
		res.append(x)
	if x - 1 not in m:
		m[x - 1] = m[x] + 1
		q.append(x - 1)
	if x + 1 not in m:
		m[x + 1] = m[x] + 1
		q.append(x + 1)
	j += 1
print(ans)
for i in res:
	print(i, end=' ')


from collections import deque
(n, m) = list(map(int, input().split()))
X = set(map(int, input().split()))
A = []
Y = set([])
for i in X:
	if i - 1 not in X:
		A.append([i - 1, i, 1])
	if i + 1 not in X:
		A.append([i + 1, i, 1])
A = deque(A)
d = 0
while m != 0:
	s = A[0]
	if s[0] not in Y:
		Y.add(s[0])
	else:
		A.popleft()
		continue
	d += s[2]
	if s[0] < s[1]:
		if s[0] - 1 in X:
			A.popleft()
		else:
			s[0] -= 1
			s[2] += 1
			A.popleft()
			A.append(s)
	elif s[0] + 1 in X:
		A.popleft()
	else:
		s[0] += 1
		s[2] += 1
		A.popleft()
		A.append(s)
	m -= 1
print(d)
print(' '.join(list(map(str, Y))))


from collections import defaultdict
(n, m) = list(map(int, input().split()))
As = sorted(list(map(int, input().split())))
d = defaultdict(int)
d2 = defaultdict(int)
d3 = defaultdict(int)
for (a, b) in zip(As, As[1:]):
	if (b + a) % 2:
		d[(b - a) // 2] += 2
		d2[a] = (b - a) // 2
		d3[b] = (b - a) // 2
	else:
		d[(b - a) // 2] += 1
		d[(b - a) // 2 - 1] += 1
		d2[a] = (b - a) // 2
		d3[b] = (b - a) // 2 - 1
d[10 ** 10] += 2
d2[As[-1]] = 10 ** 10
d3[As[0]] = 10 ** 10
ys = sorted(d.keys())
ly = len(As) * 2
c = 0
r = 0
for i in range(m + 1):
	ly -= d[i]
	if m <= c + ly:
		r += (i + 1) * (m - c)
		v = m - c
		break
	c += ly
	r += (i + 1) * ly
rs = set()
for a in As:
	if d2[a] > i and v > 0:
		kk = i + 1
		v -= 1
	else:
		kk = min(d2[a], i)
	for j in range(1, kk + 1):
		rs.add(a + j)
	if d3[a] > i and v > 0:
		kk = i + 1
		v -= 1
	else:
		kk = min(d3[a], i)
	for j in range(1, kk + 1):
		rs.add(a - j)
print(r)
print(*list(rs))


import sys, os, io
from collections import defaultdict, deque
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
dic = defaultdict(lambda : 0)
for i in x:
	dic[i] = 1
q = deque()
for i in x:
	q.append(i)
ans = []
dis = defaultdict(lambda : 0)
while m:
	curr = q.popleft()
	if dic[curr - 1] == 0:
		ans.append(curr - 1)
		dic[curr - 1] = 1
		q.append(curr - 1)
		dis[curr - 1] = dis[curr] + 1
		m -= 1
	if m == 0:
		break
	if dic[curr + 1] == 0:
		ans.append(curr + 1)
		dic[curr + 1] = 1
		q.append(curr + 1)
		dis[curr + 1] = dis[curr] + 1
		m -= 1
s = 0
for i in dis:
	s += dis[i]
print(s)
print(*ans)


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=0, func=lambda a, b: max(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
opp = []
opp.append([1, 2 * 10 ** 5 + 1, l[0], 1])
opp.append([1, 2 * 10 ** 5 + 1, l[n - 1], 0])
for i in range(1, n):
	tot = l[i] - l[i - 1]
	tot -= 1
	if tot <= 0:
		continue
	if tot % 2 == 0:
		opp.append([1, tot // 2, l[i], 1])
	else:
		opp.append([1, tot // 2 + 1, l[i], 1])
	if tot != 1:
		opp.append([1, tot // 2, l[i - 1], 0])
heapq.heapify(opp)
ans = 0
w = []
for i in range(m):
	e = heapq.heappop(opp)
	ans += e[0]
	w.append(e[2] + (-1) ** e[3] * e[0])
	e[0] += 1
	if e[0] <= e[1]:
		heapq.heappush(opp, e)
print(ans)
print(*w)


import sys, os, io
from sys import stdin
import math
from collections import defaultdict, deque
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
alphabets = list('abcdefghijklmnopqrstuvwxyz')
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieveForSmallestPrimeFactor():
	MAXN = 100001
	spf = [0 for i in range(MAXN)]
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, math.ceil(math.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
	return spf

def getPrimeFactorizationLOGN(x):
	spf = sieveForSmallestPrimeFactor()
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def si():
	return input()

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
	input = lambda : sys.stdin.readline().rstrip('\r\n')

def solve():
	(n, m) = li()
	x = li()
	d = defaultdict(lambda : -1)
	s = set(x)
	q = deque()
	for i in x:
		q.append(i)
	ans = []
	cur = 0
	res = 0
	while cur < m:
		pos = q.popleft()
		if d[pos + 1] == -1 and pos + 1 not in s:
			cur += 1
			d[pos + 1] = 1
			ans.append(pos + 1)
			q.append(pos + 1)
		if d[pos - 1] == -1 and pos - 1 not in s and (cur != m):
			cur += 1
			d[pos - 1] = 1
			ans.append(pos - 1)
			q.append(pos - 1)
	x.sort()
	ans.sort()
	for i in range(m):
		y = ans[i]
		pos = bisect_left(x, y)
		if pos == len(x):
			pos -= 1
		temp = 0
		temp = abs(y - x[pos])
		if pos > 0:
			temp = min(temp, abs(y - x[pos - 1]))
		res += temp
	print(res)
	print(*ans)
t = 1
for _ in range(t):
	solve()


a = input('').split(' ')
n = int(a[0])
m = int(a[1])
x = list(map(int, input('').split(' ')))
d = {}
for xx in x:
	d[xx] = True
i = 0
c = 0
pos = [[]]
pos.append([])
cur = 0
pos[cur] = x.copy()
ys = []
ans = 0
while i < m:
	c += 1
	pos[cur ^ 1] = []
	for k in pos[cur]:
		if k + 1 not in d:
			pos[cur ^ 1].append(k + 1)
			d[k + 1] = True
		if k - 1 not in d:
			pos[cur ^ 1].append(k - 1)
			d[k - 1] = True
	res = False
	cur = cur ^ 1
	for p in pos[cur]:
		i += 1
		ys.append(p)
		ans += c
		if i == m:
			res = True
			break
	if res:
		break
print(ans)
for h in ys:
	print(h, end=' ')


(n, m) = map(int, input().strip().split())
arr = list(map(int, input().strip().split()))
d = {}
q = []
for i in arr:
	d[i] = 0
	q.append(i)
ans = []
v = 0
index = 0
while len(ans) != m:
	x = q[index]
	if x - 1 not in d:
		d[x - 1] = d[x] + 1
		ans.append(x - 1)
		q.append(x - 1)
		v = v + d[x - 1]
	if len(ans) == m:
		break
	if x + 1 not in d:
		d[x + 1] = d[x] + 1
		ans.append(x + 1)
		q.append(x + 1)
		v = v + d[x + 1]
	index = index + 1
print(v)
print(*ans)


import heapq
heap = []
(n, m) = map(int, input().split(' '))
trees = list(map(int, input().split(' ')))
trees.sort()
data = []
for i in range(n):
	start = trees[i] - 1
	end = trees[i] + 1
	if i > 0 and trees[i - 1] + 1 == trees[i]:
		start = trees[i]
	if i < n - 1 and trees[i] + 1 == trees[i + 1]:
		end = trees[i]
	data.append([trees[i], start, end])

def find(position, start, end):
	if start == position and end == position:
		return (9999999999999999, 9999999999999999)
	elif start == position:
		return (end - position, end)
	elif end == position:
		return (position - start, start)
	target = start
	distance = position - start
	if end - position < distance:
		target = end
		distance = end - position
	return (distance, target)
for i in range(n):
	position = data[i][0]
	start = data[i][1]
	end = data[i][2]
	distance = find(position, start, end)[0]
	heapq.heappush(heap, (distance, i))
result_sum = 0
result_array = []
for i in range(m):
	(distance, index) = heapq.heappop(heap)
	position = data[index][0]
	start = data[index][1]
	end = data[index][2]
	while distance != find(position, start, end)[0]:
		new_distance = find(position, start, end)[0]
		heapq.heappush(heap, (new_distance, index))
		(distance, index) = heapq.heappop(heap)
		position = data[index][0]
		start = data[index][1]
		end = data[index][2]
	(distance, target) = find(position, start, end)
	result_sum += distance
	result_array.append(target)
	if target < position:
		if index > 0 and data[index - 1][2] == data[index][1]:
			data[index - 1][2] = data[index - 1][0]
			data[index][1] = data[index][0]
		else:
			data[index][1] -= 1
	elif target > position:
		if index < n - 1 and data[index + 1][1] == data[index][2]:
			data[index + 1][1] = data[index + 1][0]
			data[index][2] = data[index][0]
		else:
			data[index][2] += 1
	position = data[index][0]
	start = data[index][1]
	end = data[index][2]
	new_distance = find(position, start, end)[0]
	heapq.heappush(heap, (new_distance, index))
print(result_sum)
for i in result_array:
	print(i, end=' ')


from collections import deque
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
visited = set(a)
q = deque()
for i in a:
	q.append((1, i - 1))
	q.append((1, i + 1))
count = 0
result = 0
results = []
while count < k:
	(distance, now) = q.popleft()
	if now in visited:
		continue
	result += distance
	results.append(now)
	visited.add(now)
	q.append((distance + 1, now - 1))
	q.append((distance + 1, now + 1))
	count += 1
print(result)
for i in results:
	print(i, end=' ')


from collections import deque
(n, m) = map(int, input().split())
x = list(map(int, input().split()))
dists = {a: 0 for a in x}
q = deque(x)
dist = 0
res = []
while len(q) > 0:
	e = q.pop()
	if len(res) == m:
		break
	if dists[e] > 0:
		dist += dists[e]
		res.append(e)
	if e - 1 not in dists:
		dists[e - 1] = dists[e] + 1
		q.appendleft(e - 1)
	if e + 1 not in dists:
		dists[e + 1] = dists[e] + 1
		q.appendleft(e + 1)
print(dist)
print(' '.join(map(str, res)))


from sys import stdin, stdout
input = stdin.readline
from collections import deque
t = 1
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	ans = 0
	mans = []
	taken = deque(arr.copy())
	d = {}
	for i in taken:
		d[i] = 0
	while m:
		val = taken.popleft()
		if d[val]:
			ans += d[val]
			m -= 1
			mans.append(val)
		if val + 1 not in d:
			d[val + 1] = d[val] + 1
			taken.append(val + 1)
		if val - 1 not in d:
			d[val - 1] = d[val] + 1
			taken.append(val - 1)
	print(ans)
	print(*mans)


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
new = [l[0]]
for i in range(1, n - 1):
	if l[i + 1] - l[i - 1] != 2:
		new.append(l[i])
new.append(l[-1])
d = {}
for i in l:
	d[str(i)] = 1
ans = []
minans = l[0]
maxans = l[-1]
dist = 1
count = 0
while maxans - minans + 1 > len(ans) + n and len(ans) < m:
	for i in range(len(new)):
		if str(new[i] - dist) not in d:
			ans.append(new[i] - dist)
			d[str(new[i] - dist)] = 1
			if new[i] - dist < minans:
				minans = new[i] - dist
			count += dist
		if str(new[i] + dist) not in d:
			ans.append(new[i] + dist)
			d[str(new[i] + dist)] = 1
			if new[i] + dist > maxans:
				maxans = new[i] + dist
			count += dist
	new1 = [new[0]]
	for i in range(1, len(new) - 1):
		if str(new[i + 1]) in d and str(new[i - 1]) in d:
			new1.append(new[i])
	new1.append(new[-1])
	new = []
	for i in range(len(new1)):
		new.append(new1[i])
	dist += 1
if len(ans) > m:
	print(count - (dist - 1) * (len(ans) - m))
	for i in range(m):
		print(ans[i], end=' ')
	print()
elif len(ans) == m:
	print(count)
	print(*ans)
else:
	if len(ans) > 0:
		left = min(ans)
		right = max(ans)
	else:
		left = l[0]
		right = l[-1]
	rem = m - len(ans)
	dist = 1
	if rem % 2 == 0:
		for i in range(rem // 2):
			ans.append(left - dist)
			dist += 1
			count += abs(ans[-1] - l[0])
		dist = 1
		for i in range(rem // 2):
			ans.append(right + dist)
			dist += 1
			count += abs(ans[-1] - l[-1])
	else:
		for i in range(rem // 2):
			ans.append(left - dist)
			dist += 1
			count += abs(ans[-1] - l[0])
		dist = 1
		for i in range(rem // 2 + 1):
			ans.append(right + dist)
			dist += 1
			count += abs(ans[-1] - l[-1])
	print(count)
	print(*ans)


from collections import deque
(treeCount, personCount) = map(int, input().rstrip().split())
treePos = list(map(int, input().rstrip().split()))
trees = set(treePos)
q = deque([(t, 0) for t in trees])
pcount = 0
pcost = 0
ppos = set()
while len(q) > 0:
	tmp = q.popleft()
	if tmp[0] not in ppos:
		if tmp[0] + 1 not in trees:
			q.append((tmp[0] + 1, tmp[1] + 1))
		if tmp[0] - 1 not in trees:
			q.append((tmp[0] - 1, tmp[1] + 1))
		if tmp[1] > 0:
			ppos.add(tmp[0])
			pcount += 1
			pcost += tmp[1]
			if pcount == personCount:
				break
tstr = ' '.join((str(i) for i in ppos))
print(pcost)
print(tstr)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
d = {}
q = []
for c in a:
	d[c] = 1
	q.append(c)
ans = set()
v = 0
i = 0
while len(ans) < m:
	x = q[i]
	if x - 1 not in d:
		v += d[x]
		ans.add(x - 1)
		q.append(x - 1)
		d[x - 1] = d[x] + 1
	if len(ans) == m:
		break
	if x + 1 not in d:
		v += d[x]
		ans.add(x + 1)
		q.append(x + 1)
		d[x + 1] = d[x] + 1
	i += 1
print(v)
print(*ans)


(n, m) = list(map(int, input().split()))
pos = list(map(int, input().split()))
d = {}
for i in range(n):
	d[pos[i]] = 0
j = 0
ans = 0
final = []
while len(final) < m:
	p = pos[j]
	if d[p]:
		ans += d[p]
		final.append(p)
	if not p + 1 in d:
		d[p + 1] = d[p] + 1
		pos.append(p + 1)
	if not p - 1 in d:
		d[p - 1] = d[p] + 1
		pos.append(p - 1)
	j += 1
print(ans)
print(*final)


(n, m) = map(int, input().split())
q = list(map(int, input().split()))
res = []
ans = 0
d = {}
i = 0
for p in q:
	d[p] = 0
while len(q) != 0:
	if len(res) == m:
		break
	cur = q[i]
	i += 1
	if d[cur] != 0:
		ans += d[cur]
		res.append(cur)
	if cur - 1 not in d:
		d[cur - 1] = d[cur] + 1
		q.append(cur - 1)
	if cur + 1 not in d:
		d[cur + 1] = d[cur] + 1
		q.append(cur + 1)
print(ans)
print(' '.join(map(str, res)))


import heapq
(n, m) = map(int, input().split())
x = list(map(int, input().split()))
total = 0
y = list()
ocupado = set(x)
Q = [(1, arbol + h) for arbol in x for h in (-1, 1)]
while len(y) < m:
	(distancia, posicion) = heapq.heappop(Q)
	if posicion not in ocupado:
		y.append(posicion)
		total += distancia
		ocupado.add(posicion)
		heapq.heappush(Q, (distancia + 1, posicion + 1))
		heapq.heappush(Q, (distancia + 1, posicion - 1))
print(total)
print(*y)


import bisect, sys
l = input().split()
n = int(l[0])
m = int(l[1])
inf = 10 ** 15
l = input().split()
li = [inf, -inf]
for i in l:
	li.append(int(i))
li.sort()
dist = 1
ans = 0
diff = []
for i in range(n + 1):
	diff.append((li[i + 1] - li[i], li[i], li[i + 1]))
diff.sort()
diffo = []
num1 = []
num2 = []
for i in diff:
	diffo.append(i[0])
	num1.append(i[1])
	num2.append(i[2])
l = []
i = 0
done = 0
while 1:
	z = bisect.bisect_left(diffo, 2 * dist)
	for i in range(z, n + 1):
		if num1[i] == inf or num1[i] == -inf:
			continue
		if len(l) >= m:
			done = 1
			break
		ans += dist
		l.append(num1[i] + dist)
	if len(l) >= m:
		break
	z = bisect.bisect_left(diffo, 2 * dist + 1)
	for i in range(z, n + 1):
		if num2[i] == inf or num2[i] == -inf:
			continue
		if len(l) >= m:
			break
		ans += dist
		l.append(num2[i] - dist)
	if len(l) >= m:
		break
	dist += 1
print(ans)
for i in l:
	print(i, end=' ')


from collections import deque
(n, m) = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
occupied = set(x)
nearest = deque()
for tree in x:
	nearest.append((tree - 1, 1))
	nearest.append((tree + 1, 1))
res = 0
y = []
while len(y) < m:
	(pos, dist) = nearest.popleft()
	if pos in occupied:
		continue
	res += dist
	y.append(pos)
	occupied.add(pos)
	nearest.append((pos - 1, dist + 1))
	nearest.append((pos + 1, dist + 1))
print(res)
print(' '.join([str(i) for i in y]))


(n, m) = map(int, input().split())
x = list(map(int, input().split()))
visited = set(x)
y = []
frontier = x
i = 0
ans = 0
numFolks = 0
while numFolks < m:
	next = []
	for u in frontier:
		if i > 0:
			ans += i
			numFolks += 1
			y.append(u)
			if numFolks == m:
				break
		for v in (u - 1, u + 1):
			if v not in visited:
				next.append(v)
				visited.add(v)
	i += 1
	frontier = next
print(ans)
for p in y:
	print(p, end=' ')


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd
from collections import deque
(n, m) = map(int, input().split())
stack = deque()
l = list(map(int, input().split()))
s = set(l)
ans = []
for i in l:
	if i - 1 not in s:
		s.add(i - 1)
		stack.append(i - 1)
	if i + 1 not in s:
		s.add(i + 1)
		stack.append(i + 1)
count = 0
a = 0
while m > 0:
	a += 1
	for i in range(len(stack)):
		if m <= 0:
			break
		t = stack.popleft()
		ans.append(t)
		m -= 1
		count += a
		if t - 1 not in s:
			stack.append(t - 1)
			s.add(t - 1)
		if t + 1 not in s:
			stack.append(t + 1)
			s.add(t + 1)
print(count)
print(*ans)


from collections import deque
bfs_queue = deque()
(n, m) = map(int, input().split())
y = {}
ans = 0

def bfs():
	global m, ans
	while len(bfs_queue):
		if m <= 0:
			break
		af = bfs_queue.popleft()
		f = af[0]
		if y.get(f) == 0:
			if y.get(f + 1) is None:
				bfs_queue.append((f + 1, af[1] + 1))
			if y.get(f - 1) is None:
				bfs_queue.append((f - 1, af[1] + 1))
		elif y.get(f) is None:
			m -= 1
			y[f] = -1
			ans += af[1]
			if y.get(f + 1) is None:
				bfs_queue.append((f + 1, af[1] + 1))
			if y.get(f - 1) is None:
				bfs_queue.append((f - 1, af[1] + 1))
for i in map(int, input().split()):
	bfs_queue.append((i, 0))
	y[i] = 0
bfs()
print(ans)
for i in y:
	if y[i] == -1:
		print(i, end=' ')


(n, m) = [int(x) for x in input().split()]
x = [int(e) for e in input().split()]
q = []
output = []
visited = {}
for i in x:
	q.append((i, 0))
	visited[i] = True
jj = 0
res = 0
while m > 0:
	(temp, ct) = q[jj]
	jj = jj + 1
	if temp - 1 not in visited:
		visited[temp - 1] = True
		output.append(temp - 1)
		q.append((temp - 1, ct + 1))
		res += ct + 1
		m -= 1
	if m == 0:
		break
	if temp + 1 not in visited:
		visited[temp + 1] = True
		output.append(temp + 1)
		q.append((temp + 1, ct + 1))
		res += ct + 1
		m -= 1
print(res)
print(' '.join((str(p) for p in output)))


(tree, human) = list(map(int, input().split()))
treepos = list(map(int, input().split()))
dic = {}
for i in treepos:
	dic[i] = 0
num = 0
x = 0
dis = 1
res = []
while len(res) < human:
	node = treepos[x]
	if node - 1 not in dic:
		res.append(node - 1)
		treepos.append(node - 1)
		dic[node - 1] = dic[node] + 1
		num += dic[node - 1]
	if len(res) == human:
		break
	if node + 1 not in dic:
		res.append(node + 1)
		treepos.append(node + 1)
		dic[node + 1] = dic[node] + 1
		num += dic[node + 1]
	x += 1
print(num)
for i in res:
	print(i, end=' ')


(n, m) = [int(x) for x in input().split()]
x = [int(x) for x in input().split()]
x = set(x)
ans = x.copy()
ans1 = ans.copy()
dist = 1
distances = 0
while len(ans) < m + n:
	deletable = set()
	for tree in x:
		cnt = 0
		if len(ans) < m + n:
			length = len(ans)
			ans.add(tree - dist)
			if length + 1 == len(ans):
				distances += dist
			else:
				cnt += 1
		else:
			break
		if len(ans) < m + n:
			length = len(ans)
			ans.add(tree + dist)
			if length + 1 == len(ans):
				distances += dist
			else:
				cnt += 1
		else:
			break
		if cnt == 2:
			deletable.add(tree)
	x = x - deletable
	dist += 1
print(distances)
ans = ans - ans1
print(*ans)


import bisect
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
ar = list(map(int, input().split()))
se = set(ar.copy())
xx = se.copy()
ans = []
le = 0
while le < m:
	tem = set({})
	for i in xx:
		if not i + 1 in se:
			tem.add(i + 1)
			se.add(i + 1)
			le += 1
			ans.append(i + 1)
		if le == m:
			break
		if not i - 1 in se:
			tem.add(i - 1)
			se.add(i - 1)
			le += 1
			ans.append(i - 1)
		if le == m:
			break
	xx = tem.copy()
ar.sort()
count = 0
for i in ans:
	xx = bisect.bisect(ar, i)
	if xx == 0:
		count += ar[0] - i
	elif xx == n:
		count += i - ar[xx - 1]
	else:
		count += min(abs(ar[xx] - i), abs(ar[xx - 1] - i))
print(count)
print(*ans)


def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))
from queue import deque
(n, m) = [int(x) for x in input().split()]
a = [int(z) for z in input().split()]
occupiedPositions = set()
for x in a:
	occupiedPositions.add(x)
ans = []
positionQ = deque()
a.sort()
for i in range(n):
	if a[i] - 1 not in occupiedPositions:
		positionQ.append([a[i] - 1, 1])
		occupiedPositions.add(a[i] - 1)
	if a[i] + 1 not in occupiedPositions:
		positionQ.append([a[i] + 1, 1])
		occupiedPositions.add(a[i] + 1)
totalDistance = 0
while len(ans) < m:
	(pos, dis) = positionQ.popleft()
	totalDistance += dis
	ans.append(pos)
	if pos - 1 not in occupiedPositions:
		occupiedPositions.add(pos - 1)
		positionQ.append([pos - 1, dis + 1])
	if pos + 1 not in occupiedPositions:
		occupiedPositions.add(pos + 1)
		positionQ.append([pos + 1, dis + 1])
print(totalDistance)
oneLineArrayPrint(ans)


from collections import deque

def getPos(x):
	return (x - 1, x + 1)
(n, m) = map(int, input().split())
treePos = list(map(int, input().split()))
occ = dict()
for pos in treePos:
	occ[pos] = 0
q = deque(treePos)
assigned = 0
res = 0
men = list()
while True:
	s = q.popleft()
	d = occ[s] + 1
	(left, right) = getPos(s)
	if left not in occ:
		assigned += 1
		men.append(left)
		occ[left] = d
		q.append(left)
		res += d
	if assigned == m:
		break
	if right not in occ:
		assigned += 1
		men.append(right)
		occ[right] = d
		q.append(right)
		res += d
	if assigned == m:
		break
print(res)
for man in men:
	print(man, end=' ')


import sys
input = sys.stdin.readline
from collections import deque

class Graph(object):

	def __init__(self, n, d):
		self.n = n
		self.graph = [[] for i in range(n)]
		self.parent = [-1 for i in range(n)]
		self.directed = d

	def addEdge(self, x, y):
		self.graph[x].append(y)
		if not self.directed:
			self.graph[y].append(x)

	def bfs(self, root):
		self.parent = [-1 for i in range(self.n)]
		queue = [root]
		queue = deque(queue)
		vis = [0] * self.n
		while len(queue) != 0:
			element = queue.popleft()
			vis[element] = 1
			for i in self.graph[element]:
				if vis[i] == 0:
					queue.append(i)
					self.parent[i] = element

	def dfs(self, root, ans):
		stack = [root]
		vis = [0] * self.n
		stack2 = []
		while len(stack) != 0:
			element = stack.pop()
			if vis[element]:
				continue
			vis[element] = 1
			stack2.append(element)
			for i in self.graph[element]:
				if vis[i] == 0:
					self.parent[i] = element
					stack.append(i)
		while len(stack2) != 0:
			element = stack2.pop()
			m = 0
			for i in self.graph[element]:
				if i != self.parent[element]:
					m += ans[i]
			ans[element] = m
		return ans

	def shortestpath(self, source, dest):
		self.bfs(source)
		path = [dest]
		while self.parent[path[-1]] != -1:
			path.append(parent[path[-1]])
		return path[::-1]

	def ifcycle(self):
		self.bfs(0)
		queue = [0]
		vis = [0] * n
		queue = deque(queue)
		while len(queue) != 0:
			element = queue.popleft()
			vis[element] = 1
			for i in graph[element]:
				if vis[i] == 1 and i != parent[element]:
					return True
				if vis[i] == 0:
					queue.append(i)
					vis[i] = 1
		return False

	def reroot(self, root, ans):
		stack = [root]
		vis = [0] * n
		while len(stack) != 0:
			e = stack[-1]
			if vis[e]:
				stack.pop()
				continue
			vis[e] = 1
			for i in graph[e]:
				if not vis[e]:
					stack.append(i)
			if self.parent[e] == -1:
				continue

	def multibfs(self, q, s):
		q = deque(q)
		d = set(q)
		dist = {}
		for i in d:
			dist[i] = 0
		while len(q) != 0:
			e = q.popleft()
			if e - 1 not in d:
				d.add(e - 1)
				ans.append(e - 1)
				q.append(e - 1)
				dist[e - 1] = dist[e] + 1
				s += dist[e - 1]
			if len(ans) == m:
				return s
			if e + 1 not in d:
				d.add(e + 1)
				ans.append(e + 1)
				q.append(e + 1)
				dist[e + 1] = dist[e] + 1
				s += dist[e + 1]
			if len(ans) == m:
				return s
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
g = Graph(n, True)
ans = []
print(g.multibfs(a, 0))
print(*ans)


from collections import deque
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
t1 = min(l)
t2 = max(l)
d = {}
q = []
ans = []
dis = 0
q = deque(q)
d1 = 0
for i in range(len(l)):
	d[l[i]] = 1
	q.append((l[i], 1))
while len(ans) < m:
	(pos, d1) = q.popleft()
	if pos - 1 in d:
		pass
	else:
		dis = dis + d1
		d[pos - 1] = d[pos] + 1
		q.append((pos - 1, d[pos - 1]))
		ans.append(pos - 1)
	if len(ans) == m:
		break
	if pos + 1 in d:
		pass
	else:
		dis = dis + d1
		d[pos + 1] = d[pos] + 1
		q.append((pos + 1, d[pos + 1]))
		ans.append(pos + 1)
print(dis)
print(*ans)


from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
from collections import defaultdict as dd, deque

def data():
	return sys.stdin.readline().strip()

def mdata():
	return map(int, data().split())
mod = int(1000000000.0 + 7)
(n, m) = mdata()
x = list(mdata())
d = dd(int)
for i in x:
	d[i] = 1
s = set(x)
cnt = m
l = []
ans = 0
t = 1
while cnt > 0:
	s1 = set()
	for i in s:
		if d[i + 1] == 0:
			s1.add(i + 1)
			d[i + 1] = 1
			ans += t
			cnt -= 1
			l.append(i + 1)
		if cnt == 0:
			break
		if d[i - 1] == 0:
			s1.add(i - 1)
			d[i - 1] = 1
			ans += t
			cnt -= 1
			l.append(i - 1)
		if cnt == 0:
			break
	t += 1
	s = s1
print(ans)
print(*l)


from queue import deque
(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort()
used = set(arr)
q = deque()
for i in range(n):
	q.append([arr[i] - 1, 1, -1])
	q.append([arr[i] + 1, 1, 1])
ret = []
s = 0
while m:
	(x, l, dr) = q.popleft()
	a = x + dr
	if not a in used:
		q.append([a, l + 1, dr])
	if not x in used:
		used.add(x)
		ret.append(x)
		m -= 1
		s += l
print(s)
print(*ret)


import os, sys, math
import collections
if os.path.exists('testing'):
	name = os.path.basename(__file__)
	if name.endswith('.py'):
		name = name[:-3]
	src = open(name + '.txt', encoding='utf8')
	input = src.readline

def solve():
	global xs
	xs = list(sorted(xs))
	min_region_index = xs[0] - 1
	max_region_index = xs[-1] + 1
	border_index = 2 * 10 ** 9
	prev = None
	regions = []
	for x in xs:
		if prev is not None and x - prev > 1:
			regions.append((prev + 1, x - 1))
		prev = x
	ys = []
	min_dist = 0
	current_dist = 1
	while len(ys) < m:
		region_index = 0
		if len(ys) < m and -border_index <= min_region_index:
			ys.append(min_region_index)
			min_dist += current_dist
			min_region_index -= 1
		if len(ys) < m and max_region_index <= border_index:
			ys.append(max_region_index)
			min_dist += current_dist
			max_region_index += 1
		while len(ys) < m and region_index < len(regions):
			(a, b) = regions[region_index]
			if a < b and len(ys) + 2 <= m:
				ys.append(a)
				ys.append(b)
				a += 1
				b -= 1
				min_dist += current_dist * 2
				if a <= b:
					regions[region_index] = (a, b)
				else:
					regions[region_index] = regions[-1]
					regions.pop()
					continue
			else:
				ys.append(a)
				min_dist += current_dist
				regions[region_index] = regions[-1]
				regions.pop()
				continue
			region_index += 1
		current_dist += 1
	return (min_dist, ys)

def integers():
	return map(int, input().strip().split())

def array_of_integers(q):
	return [tuple(map(int, input().strip().split())) for _ in range(q)]
(n, m) = integers()
xs = list(integers())
(res, ys) = solve()
print(res)
print(' '.join(map(str, ys)))


from collections import deque
import sys
input = sys.stdin.readline
t = 1
for testcase in range(t):
	(n, m) = map(int, input().split())
	x = list(map(int, input().split()))
	res = []
	val = 0
	s = dict()
	for e in x:
		s[e] = 0
	tank = deque(x)
	dg = 10 ** 10
	while len(res) < m:
		q = tank.popleft()
		if not q - 1 in s:
			s[q - 1] = s[q] + 1
			res.append(q - 1)
			val += s[q] + 1
			tank.append(q - 1)
		if len(res) < m and (not q + 1 in s):
			s[q + 1] = s[q] + 1
			res.append(q + 1)
			val += s[q] + 1
			tank.append(q + 1)
	print(val)
	print(*res)


from sys import stdout

def solution():
	(a, b) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	points = set(arr)
	s = set()
	i = 1
	total = 0
	while len(s) < b:
		temp = set()
		for v in arr:
			p = v - i
			if p not in points:
				s.add(p)
				points.add(p)
				temp.add(v)
				total += i
				if len(s) == b:
					break
			p = v + i
			if p not in points:
				s.add(p)
				points.add(p)
				temp.add(v)
				total += i
				if len(s) == b:
					break
		i += 1
		arr = frozenset(temp)
	stdout.write('{}\n{}'.format(total, ' '.join(map(str, s))))
solution()


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bfs(src):
	from collections import deque
	que = deque()
	for x in src:
		que.append((x, 0))
	dist = {}
	while len(dist) < N + M:
		(u, c) = que.popleft()
		if u in dist:
			continue
		dist[u] = c
		que.append((u - 1, c + 1))
		que.append((u + 1, c + 1))
	return dist
(N, M) = MAP()
A = LIST()
res = bfs(A)
ans = []
sm = 0
for (k, v) in res.items():
	if v != 0:
		sm += v
		ans.append(k)
print(sm)
print(*ans)


from collections import defaultdict, deque

def put():
	return map(int, input().split())
(n, m) = put()
l = list(put())
vis = defaultdict()
q = deque()
for i in l:
	vis[i] = 1
	for j in [i - 1, i + 1]:
		q.append((j, 1))
(ans, l) = (0, [])
while q and m > 0:
	(i, d) = q.popleft()
	if i in vis:
		continue
	vis[i] = 1
	m -= 1
	l.append(i)
	ans += d
	for j in [i - 1, i + 1]:
		q.append((j, d + 1))
print(ans)
print(*l)


from collections import deque
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
delta = {x: 1 for x in a}
used = set(a)
dq = deque(a)
ans = []
cost = 0
dame = 0
for i in range(m):
	while dq[0] + delta[dq[0]] in used:
		if delta[dq[0]] < 0:
			if dame:
				dq.popleft()
			else:
				delta[dq[0]] = -delta[dq[0]] + 1
				dq.rotate(-1)
			dame = 0
		else:
			delta[dq[0]] *= -1
			dame = 1
	ans.append(dq[0] + delta[dq[0]])
	used.add(dq[0] + delta[dq[0]])
	cost += abs(delta[dq[0]])
	dame = 0
	if delta[dq[0]] < 0:
		delta[dq[0]] = -delta[dq[0]] + 1
		dq.rotate(-1)
	else:
		delta[dq[0]] *= -1
print(cost)
print(*ans)


(n, m) = map(int, input().split())
x = list(map(int, input().split()))
from collections import deque
dist = {}
y = []
queue = deque()
for t in x:
	dist[t] = 0
	queue.append(t)
ans = 0
while queue:
	cur = queue.popleft()
	if len(y) == m:
		break
	if dist[cur] > 0:
		ans += dist[cur]
		y.append(cur)
	for v in (cur - 1, cur + 1):
		if v not in dist:
			dist[v] = dist[cur] + 1
			queue.append(v)
print(ans)
for p in y:
	print(p, end=' ')


from collections import deque
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
s = set()
s1 = set()
d = deque()
for i in a:
	d.append(i)
	s.add(i)
	s1.add(i)
d.append(None)
level = 0
ans = []
an = 0
while m > 0:
	t = d.popleft()
	if t == None:
		level += 1
		d.append(None)
		continue
	if t in s1:
		if t - 1 not in s:
			s.add(t - 1)
			d.append(t - 1)
		if t + 1 not in s:
			s.add(t + 1)
			d.append(t + 1)
	else:
		m -= 1
		ans.append(t)
		an += level
		if t - 1 not in s:
			s.add(t - 1)
			d.append(t - 1)
		if t + 1 not in s:
			s.add(t + 1)
			d.append(t + 1)
print(an)
print(*ans)


from collections import defaultdict

def christmas(n, m, A):
	d = defaultdict(int)
	q = []
	for i in A:
		d[i] = 0
		q.append(i)
	mini = 0
	res = []
	i = 0
	while len(res) < m:
		k = q[i]
		if k - 1 not in d:
			d[k - 1] = d[k] + 1
			mini += d[k - 1]
			q.append(k - 1)
			res.append(k - 1)
		if len(res) == m:
			break
		if k + 1 not in d:
			d[k + 1] = d[k] + 1
			mini += d[k + 1]
			q.append(k + 1)
			res.append(k + 1)
		i += 1
	print(mini)
	print(*res)
(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
christmas(n, m, arr)


(n, y) = map(int, input().split())
q = list(map(int, input().split()))
(v, m, ans, j) = ([], {}, 0, 0)
for i in q:
	m[i] = 0
while len(v) != y:
	x = q[j]
	if m[x]:
		ans += m[x]
		v.append(x)
	try:
		tmp = m[x + 1]
	except:
		m[x + 1] = m[x] + 1
		q.append(x + 1)
	try:
		tmp = m[x - 1]
	except:
		m[x - 1] = m[x] + 1
		q.append(x - 1)
	j += 1
print(ans)
for i in v:
	print(i, end=' ')


(n, m) = map(int, input().split())
lis = list(map(int, input().split()))
ans = i = 0
aa = []
q = {}
for i in lis:
	q[i] = 0
i = 0
while len(aa) != m:
	k = lis[i]
	if q[k]:
		ans += q[k]
		aa.append(k)
	if k - 1 not in q:
		q[k - 1] = q[k] + 1
		lis.append(k - 1)
	if k + 1 not in q:
		q[k + 1] = q[k] + 1
		lis.append(k + 1)
	i += 1
print(ans)
print(*aa)


import sys
input = sys.stdin.buffer.readline
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
mp = {}
q = []
for i in a:
	q.append(i)
	mp[i] = 0
(ans, res, i) = ([], 0, 0)
while len(ans) < m:
	x = q[i]
	for k in [-1, 1]:
		if x + k not in mp:
			mp[x + k] = mp[x] + 1
			res += mp[x + k]
			q.append(x + k)
			ans.append(x + k)
		if len(ans) == m:
			break
	i += 1
print(res)
print(*ans)


from collections import deque
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
x = deque(list(map(int, input().split())))
(end, now) = (0, set())
for i in x:
	now.add(i)
(ans, y, cnt) = (0, [], 0)
d = 1
while cnt < m:
	for _ in range(n - end):
		c = x.popleft()
		if c + d in now and c - d in now:
			end += 1
			continue
		if not c + d in now:
			now.add(c + d)
			cnt += 1
			ans += d
			y.append(c + d)
		if cnt == m:
			break
		if not c - d in now:
			now.add(c - d)
			cnt += 1
			ans += d
			y.append(c - d)
		if cnt == m:
			break
		x.append(c)
	d += 1
print(ans)
print(*y)


import sys
input = sys.stdin.buffer.readline
from collections import deque
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
dict = {}
stack = []
for i in range(n):
	dict[a[i]] = 1
for i in range(n):
	if a[i] + 1 not in dict:
		stack.append([a[i] + 1, 1, 1])
	if a[i] - 1 not in dict:
		stack.append([a[i] - 1, -1, -1])
store = []
stack = deque(stack)
count = 0
add = 0
while count < m:
	(x, y, z) = stack.popleft()
	if z < 0 and x not in dict:
		add += abs(y)
		store.append(x)
		stack.append([x - 1, y - 1, -1])
		dict[x] = 1
		count += 1
	elif z > 0 and x not in dict:
		add += abs(y)
		store.append(x)
		stack.append([x + 1, y + 1, 1])
		dict[x] = 1
		count += 1
print(add)
for i in range(m):
	print(store[i], end=' ')
print()


(n, m) = map(int, input().split())
v = list(map(int, input().split()))
ans = []
v1 = []
mp = {}
for i in range(0, n):
	v1.append(v[i])
	mp[v[i]] = 1
pz = 0
sol = 0
last = n
while True:
	val = v1[pz]
	pz += 1
	if mp.get(val - 1) == None:
		ans.append(val - 1)
		sol += mp[val]
		mp[val - 1] = mp[val] + 1
		v1.append(val - 1)
	if len(ans) == m:
		break
	if mp.get(val + 1) == None:
		ans.append(val + 1)
		sol += mp[val]
		mp[val + 1] = mp[val] + 1
		v1.append(val + 1)
	if len(ans) == m:
		break
print(str(sol))
print(*ans)


from collections import deque
(n, m) = map(int, input().split())
queue = deque([])
vst = set()
for k in map(int, input().split()):
	vst.add(k)
	queue.append((k, 0))
ans = 0
ans_L = []
cnt = 0
while queue:
	(x, step) = queue.popleft()
	for dx in [1, -1]:
		X = x + dx
		if X not in vst:
			cnt += 1
			vst.add(X)
			ans += step + 1
			ans_L.append(X)
			queue.append((X, step + 1))
		if cnt == m:
			break
	if cnt == m:
		break
print(ans)
print(*ans_L)


(n, m) = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]
S = set()
Q = []
hd = 0
for i in x:
	Q.append([i, 0])
	S.add(i)
ans = []
res = 0
while len(ans) < m:
	t = Q[hd]
	hd += 1
	if not S.__contains__(t[0] - 1):
		S.add(t[0] - 1)
		Q.append([t[0] - 1, t[1] + 1])
	if not S.__contains__(t[0] + 1):
		S.add(t[0] + 1)
		Q.append([t[0] + 1, t[1] + 1])
	if t[1]:
		ans.append(t[0])
		res += t[1]
print(res)
for i in range(m):
	print(ans[i], end=' ')


from collections import deque
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
dc = dict()
q = deque([])
for i in range(n):
	dc[arr[i]] = 1
for i in range(n):
	if arr[i] - 1 not in dc:
		dc[arr[i] - 1] = 1
		q.append([arr[i] - 1, 1, 'l'])
	if arr[i] + 1 not in dc:
		dc[arr[i] + 1] = 1
		q.append([arr[i] + 1, 1, 'r'])
ans = list()
dist = 0
i = 0
while i < m:
	temp = q.popleft()
	p = temp[0]
	dist += temp[1]
	dir = temp[2]
	ans.append(temp[0])
	i += 1
	if dir == 'l':
		if p - 1 not in dc:
			q.append([p - 1, temp[1] + 1, 'l'])
			dc[p - 1] = 1
	if dir == 'r':
		if p + 1 not in dc:
			q.append([p + 1, temp[1] + 1, 'r'])
			dc[p + 1] = 1
print(dist)
for i in range(len(ans)):
	print(ans[i], end=' ')


import sys
from operator import itemgetter

def input():
	return sys.stdin.readline().strip()
(n, m) = list(map(int, input().split()))
trees = set(map(int, input().split()))
occ = set(trees)
newadd = set()
for x in trees:
	if x + 1 not in occ:
		newadd.add((x + 1, 1))
	if x - 1 not in occ:
		newadd.add((x - 1, 1))
anspos = []
ans = 0
while m > 0:
	newnewadd = set()
	while m > 0 and len(newadd) > 0:
		(x, diff) = newadd.pop()
		if x in occ:
			continue
		occ.add(x)
		anspos.append(x)
		ans += diff
		if x + 1 not in occ:
			newnewadd.add((x + 1, diff + 1))
		if x - 1 not in occ:
			newnewadd.add((x - 1, diff + 1))
		m -= 1
	newadd = newnewadd
print(ans)
print(*anspos)


import math
(n, m) = list(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
ax = []
otrs = sorted([[nc, nc, nc] for nc in a], key=lambda x: x[1])
mp = 0
r = 0
while mp < m:
	otrs_r = []
	l_used = 0
	for i in range(len(otrs)):
		if mp >= m:
			break
		used = False
		if i == 0 or otrs[i - 1][2] < otrs[i][0] - 1:
			otrs[i][0] -= 1
			r += abs(otrs[i][1] - otrs[i][0])
			mp += 1
			ax.append(otrs[i][0])
			if mp == m:
				break
			used = True
		if i == len(otrs) - 1 or otrs[i][2] + 1 < otrs[i + 1][0]:
			otrs[i][2] += 1
			r += abs(otrs[i][2] - otrs[i][1])
			mp += 1
			used = True
			ax.append(otrs[i][2])
			if mp == m:
				break
		if used:
			otrs_r += [otrs[i]]
			l_used = i
		else:
			otrs[l_used][2] = otrs[i][2]
	otrs = otrs_r
print(r)
for i in range(m):
	print(ax[i], end=' ')
print()


from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
import random

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def StoI():
	return [ord(i) - 97 for i in input()]

def ItoS(nn):
	return chr(nn + 97)

def GI(V, E, Directed=False, index=0):
	org_inp = []
	g = [[] for i in range(n)]
	for i in range(E):
		inp = LI()
		org_inp.append(inp)
		if index == 0:
			inp[0] -= 1
			inp[1] -= 1
		if len(inp) == 2:
			(a, b) = inp
			g[a].append(b)
			if not Directed:
				g[b].append(a)
		elif len(inp) == 3:
			(a, b, c) = inp
			aa = (inp[0], inp[2])
			bb = (inp[1], inp[2])
			g[a].append(bb)
			if not Directed:
				g[b].append(aa)
	return (g, org_inp)

def bit_combination(k, n=2):
	rt = []
	for tb in range(n ** k):
		s = [tb // n ** bit % n for bit in range(k)]
		rt += [s]
	return rt

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
YN = ['Yes', 'No']
mo = 10 ** 9 + 7
inf = float('inf')
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
input = lambda : sys.stdin.readline().rstrip()

def ran_input():
	import random
	n = random.randint(4, 16)
	(rmin, rmax) = (1, 10)
	a = [random.randint(rmin, rmax) for _ in range(n)]
	return (n, a)
show_flg = False
show_flg = True
ans = 0
(n, m) = LI()
q = LI()
mp = dict()
for i in q:
	mp[i] = 0
sd = 0
ans = []
while q:
	for i in q:
		for d in [-1, 1]:
			if i + d not in mp:
				q.append(i + d)
				mp[i + d] = mp[i] + 1
				ans.append(i + d)
				sd += mp[i + d]
				m -= 1
				if m == 0:
					print(sd)
					print(*ans)
					exit()


def main():

	class node:

		def __init__(self, val):
			self.val = val
			self.next = None
	(n, m) = map(int, input().strip().split())
	A = sorted(list(map(int, input().strip().split())))
	sa = set(A)
	L = [node(A[i]) for i in range(n)]
	for i in range(n - 1):
		L[i].next = L[i + 1]
	p = set()
	x = 0
	flag = 0
	d = 0
	np = 0
	while flag == 0:
		x += 1
		node = L[0]
		while node != None and flag == 0:
			i = node.val
			t1 = 0
			t2 = 0
			if (i - x in p) == False and (i - x in sa) == False:
				p.add(i - x)
				d += x
				np += 1
				if np == m:
					flag = 1
					break
				t1 = 1
			if (i + x in p) == False and (i + x in sa) == False:
				p.add(i + x)
				d += x
				np += 1
				if np == m:
					flag = 1
					break
				t2 = 1
			if t1 == 0 and t2 == 0:
				(node.val, node.next) = (node.next.val, node.next.next)
			else:
				node = node.next
	p = list(p)
	print(d)
	print(' '.join([str(i) for i in p]))
main()


from collections import defaultdict
(n, m) = map(int, input().split())
c = list(map(int, input().split()))
d = defaultdict(int)
q = []
for k in c:
	d[k] = 0
	q.append(k)
ans = []
v = 0
i = 0
while len(ans) < m:
	x = q[i]
	if x - 1 not in d:
		d[x - 1] = d[x] + 1
		v += d[x - 1]
		q.append(x - 1)
		ans.append(x - 1)
	if len(ans) == m:
		break
	if x + 1 not in d:
		d[x + 1] = d[x] + 1
		v += d[x + 1]
		ans.append(x + 1)
		q.append(x + 1)
	i += 1
print(v)
print(*ans)


from sys import stdin, stdout
from heapq import heappush, heappop

def main():
	arr = list(map(int, stdin.readline().split()))
	tree = list(map(int, stdin.readline().split()))
	tree.sort()
	people = arr[1]
	heaper = []
	standing_list = list()
	cost = 0
	done = 0
	smallest = 0
	for (i, x) in enumerate(tree):
		if i == 0:
			continue
		heappush(heaper, (tree[i] - tree[i - 1] - 1, tree[i - 1], tree[i]))
	while done < people:
		smallest += 1
		while heaper and heaper[0][1] + smallest >= heaper[0][2] - smallest:
			temp_pop = heappop(heaper)
			if temp_pop[1] + smallest == temp_pop[2] - smallest:
				done += 1
				cost += smallest
				standing_list.append(temp_pop[1] + smallest)
				if done >= people:
					break
		if done >= people:
			break
		if len(heaper) > 0:
			for x in heaper:
				done += 2
				cost += smallest * 2
				standing_list.append(x[1] + smallest)
				standing_list.append(x[2] - smallest)
				if done >= people:
					break
		if done >= people:
			break
		standing_list.append(tree[0] - smallest)
		done += 1
		cost += smallest
		standing_list.append(tree[-1] + smallest)
		done += 1
		cost += smallest
	while done > people:
		cost -= smallest
		del standing_list[-1]
		done -= 1
	stdout.write(str(cost) + '\n')
	stdout.write(' '.join(map(str, standing_list)))
main()


import sys
from collections import defaultdict
from collections import deque
import heapq
vis = defaultdict(int)
(n, m) = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
q = deque()
heap = []
for i in range(len(arr)):
	heapq.heappush(heap, [0, arr[i]])
	vis[arr[i]] = 1
ans = []
dis = 0
while m > 0:
	(d, a) = heapq.heappop(heap)
	if vis[a + 1] == 0:
		m -= 1
		vis[a + 1] = 1
		dis += d + 1
		ans.append(a + 1)
		heapq.heappush(heap, [d + 1, a + 1])
	if vis[a - 1] == 0 and m > 0:
		m -= 1
		vis[a - 1] = 1
		dis += d + 1
		ans.append(a - 1)
		heapq.heappush(heap, [d + 1, a - 1])
print(dis)
print(*ans)


import string
from collections import defaultdict, Counter
from math import sqrt, log10, log2, log, gcd, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations_with_replacement
import sys, io, os
input = sys.stdin.readline
sys.setrecursionlimit(10000)
mod = int(pow(10, 7) + 9)
inf = float('inf')

def get_list():
	return [int(i) for i in input().split()]

def yn(a):
	print('YES' if a else 'NO', flush=False)
t = 1
for i in range(t):
	(n, m) = get_list()
	y = get_list()
	yset = set(y)
	occupied = set(y)
	res = 0
	dist = 1
	newlist = y
	while len(occupied) < n + m:
		traverse = newlist
		newlist = []
		for j in traverse:
			prevres = res
			if j - dist not in occupied:
				occupied.add(j - dist)
				res += dist
			if len(occupied) == n + m:
				break
			if j + dist not in occupied:
				occupied.add(j + dist)
				res += dist
			if len(occupied) == n + m:
				break
			if prevres != res:
				newlist.append(j)
		dist += 1
	answer = [i for i in occupied if i not in yset]
	print(res)
	print(*answer)


import math
import time
from collections import defaultdict, deque
from sys import stdin, stdout
from bisect import bisect_left, bisect_right
from queue import PriorityQueue
import sys

class Graph:

	def __init__(self, n):
		self.graph = defaultdict(lambda : [])
		self.vertices = n
		self.toposorted = []

	def addEdge(self, a, b):
		self.graph[a].append(b)

	def cycleUntill(self, visited, curr, parent):
		visited[curr] = True
		for i in self.graph[curr]:
			if not visited[i]:
				if self.cycleUntill(visited, i, curr):
					return True
			elif i != parent:
				return True
		return False

	def cycle(self):
		n = self.vertices
		visited = [False] * (n + 2)
		for i in range(1, n + 1):
			if not visited[i]:
				if self.cycleUntill(visited, i, -1):
					return True
		return False

	def topologicalSort(self):
		in_degree = [0] * (self.vertices + 10)
		for i in self.graph:
			for j in self.graph[i]:
				in_degree[j] += 1
		queue = deque()
		for i in range(1, self.vertices + 1):
			if in_degree[i] == 0:
				queue.append(i)
		cnt = 0
		while queue:
			u = queue.popleft()
			self.toposorted.append(u)
			for i in self.graph[u]:
				in_degree[i] -= 1
				if in_degree[i] == 0:
					queue.append(i)
			cnt += 1
		if cnt != self.vertices:
			return False
		else:
			return True
(n, m) = map(int, stdin.readline().split())
a = list(map(int, stdin.readline().split()))
dist = defaultdict(lambda : 0)
q = deque()
done = set()
for i in a:
	q.append(i)
	done.add(i)
ans = []
val = 0
while len(q) > 0:
	if len(ans) == m:
		break
	temp = q.popleft()
	if dist[temp] != 0:
		val += dist[temp]
		ans.append(temp)
	if temp - 1 not in done:
		dist[temp - 1] = dist[temp] + 1
		q.append(temp - 1)
		done.add(temp - 1)
	if temp + 1 not in done:
		dist[temp + 1] = dist[temp] + 1
		q.append(temp + 1)
		done.add(temp + 1)
print(val)
print(*ans)


from collections import deque

def solve():
	input_str = input().split()
	n = int(input_str[0])
	m = int(input_str[1])
	pos = input().split()
	seen = set([int(x) for x in pos])
	queue = deque([int(x) for x in pos])
	total_dist = 0
	cur_dist = 0
	ans = []
	exitf = False
	while queue:
		for i in range(len(queue)):
			cur = queue.popleft()
			if cur_dist > 0:
				total_dist += cur_dist
				ans.append(cur)
				if len(ans) == m:
					exitf = True
					break
			if cur - 1 not in seen:
				seen.add(cur - 1)
				queue.append(cur - 1)
			if cur + 1 not in seen:
				seen.add(cur + 1)
				queue.append(cur + 1)
		cur_dist += 1
		if exitf == True:
			break
	print(total_dist)
	for i in range(m):
		print(ans[i], end=' ')
	return 0
solve()


import collections
import heapq
(n, m) = map(int, input().split())
occupied = set(map(int, input().split()))
q = collections.deque(set([(1, x - 1) for x in occupied if x - 1 not in occupied] + [(1, x + 1) for x in occupied if x + 1 not in occupied]))
for (_, x) in q:
	occupied.add(x)
ans = []
tot = 0
while len(ans) < m:
	(dist, x) = q.popleft()
	tot += dist
	ans.append(x)
	if x - 1 not in occupied:
		q.append((dist + 1, x - 1))
		occupied.add(x - 1)
	if x + 1 not in occupied:
		q.append((dist + 1, x + 1))
		occupied.add(x + 1)
print(tot)
print(' '.join(map(str, ans)))


from collections import deque
(n, m) = map(int, input().split())
l = set(list(map(int, input().split())))
positions = deque([(x, 0) for x in l])
people = set()
dist = 0
while len(people) != m:
	(p, d) = positions.popleft()
	if p + 1 not in people and p + 1 not in l:
		positions.append((p + 1, d + 1))
	if p - 1 not in people and p - 1 not in l:
		positions.append((p - 1, d + 1))
	if d != 0:
		if p not in people:
			people.add(p)
			dist += d
print(dist)
print(' '.join((str(x) for x in people)))


from fractions import Fraction
import sys
import bisect
import heapq
from math import *
from collections import Counter as counter
from itertools import combinations as comb
from itertools import permutations as permutate
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
mod = 1000000007

def inp():
	return sys.stdin.readline().strip()

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def graph(vertex):
	return [[] for i in range(0, vertex + 1)]

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(a, b):
	ans = 1
	while b > 0:
		if b % 2 == 1:
			ans *= a
		a *= a
		b //= 2
	return ans

def solve():
	(n, k) = sep()
	a = lis()
	prsn = {}
	for i in range(0, n):
		prsn[a[i]] = 0
	cnt = 0
	index = 0
	while cnt < k:
		curr = a[index]
		if prsn.get(curr - 1) == None:
			prsn[curr - 1] = prsn[curr] + 1
			a.append(curr - 1)
			cnt += 1
		if cnt == k:
			break
		if prsn.get(curr + 1) == None:
			prsn[curr + 1] = prsn[curr] + 1
			a.append(curr + 1)
			cnt += 1
		index += 1
	ans = 0
	lol = []
	for i in prsn:
		if prsn[i] != 0:
			lol.append(i)
			ans += prsn[i]
	out(ans)
	nextline()
	printlist(lol)
testcase(1)


import sys
input = sys.stdin.readline
import heapq as hp
(N, M) = map(int, input().split())
A = list(map(int, input().split()))
checked = set(A)
q = []
for a in A:
	xs = [a + 1, a - 1]
	for x in xs:
		if not x in checked:
			hp.heappush(q, (1, x))
			checked.add(x)
S = 0
ans = []
for _ in range(M):
	(s, ind) = hp.heappop(q)
	S += s
	ans.append(ind)
	xs = [ind + 1, ind - 1]
	for x in xs:
		if not x in checked:
			hp.heappush(q, (s + 1, x))
			checked.add(x)
print(S)
print(*ans)


from collections import deque
(n, m) = map(int, input().split())
listt = list(map(int, input().split()))
que = deque(listt)
dictt = dict()
for i in range(n):
	dictt[listt[i]] = 0
summ = 0
while m > 0:
	temp = que.popleft()
	try:
		zxcv = dictt[temp + 1]
	except:
		dictt[temp + 1] = dictt[temp] + 1
		summ += dictt[temp + 1]
		que.append(temp + 1)
		m -= 1
	if not m > 0:
		break
	try:
		zxcv = dictt[temp - 1]
	except:
		dictt[temp - 1] = dictt[temp] + 1
		summ += dictt[temp - 1]
		que.append(temp - 1)
		m -= 1
print(summ)
ans = list(dictt.keys())
for i in range(n, len(ans)):
	print(ans[i], end=' ')


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
from copy import deepcopy
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inps():
	return sys.stdin.readline()

def inpsl(x):
	tmp = sys.stdin.readline()
	return list(tmp[:x])

def err(x):
	print(x)
	exit()
(n, m) = inpl()
a = inpl()
a.sort()
seen = set(a)
q = deque()
for x in a:
	if not x - 1 in seen:
		q.append(x - 1)
		seen.add(x - 1)
	if not x + 1 in seen:
		q.append(x + 1)
		seen.add(x + 1)
res = []
dist = 0
for _ in range(m):
	now = q.popleft()
	it = bisect_left(a, now)
	mi = abs(a[it] - now) if 0 <= it < n else INF
	if it - 1 >= 0:
		mi = min(mi, abs(a[it - 1] - now))
	if it + 1 < n:
		mi = min(mi, abs(a[it + 1] - now))
	dist += mi
	res.append(now)
	if not now - 1 in seen:
		q.append(now - 1)
		seen.add(now - 1)
	if not now + 1 in seen:
		q.append(now + 1)
		seen.add(now + 1)
print(dist)
print(*res)


import sys
from collections import deque
reader = (line.rstrip() for line in sys.stdin)
input = reader.__next__
(n, m) = map(int, input().split())
xs = list(map(int, input().split()))
xs.sort()
spot = deque()
for (i, x) in enumerate(xs):
	if i == 0 or xs[i - 1] + 1 < x:
		spot.append((x, -1, 1))
	if i == n - 1 or x + 1 < xs[i + 1]:
		spot.append((x, 1, 1))
k = 0
res = 0
ans = []
while k < m:
	(pos, dir1, dist1) = spot.popleft()
	if dir1 > 0:
		(nxt, dir2, dist2) = spot.popleft()
		if pos + 1 != nxt:
			spot.appendleft((nxt, dir2, dist2))
			k += 1
			res += dist1
			ans.append(pos + 1)
			spot.append((pos + 1, dir1, dist1 + 1))
	else:
		(prev, dir2, dist2) = spot.pop()
		if pos - 1 != prev:
			spot.append((prev, dir2, dist2))
			k += 1
			res += dist1
			ans.append(pos - 1)
			spot.append((pos - 1, dir1, dist1 + 1))
print(res)
print(*ans)


import collections as col
(n, m) = map(int, input().split())
Burn = col.deque(map(int, input().split()))
B = list()
U1 = set(Burn)
Used = set(Burn)
k = 1
cnt = 0
ans = 0
while cnt != m:
	for i in Burn:
		if i - 1 not in Used:
			Used.add(i - 1)
			B.append(i - 1)
			cnt += 1
			ans += k
		if cnt == m:
			break
		if i + 1 not in Used:
			Used.add(i + 1)
			B.append(i + 1)
			cnt += 1
			ans += k
		if cnt == m:
			break
	k += 1
	Burn = B.copy()
	B = list()
Used = Used.difference(U1)
print(ans)
for i in Used:
	print(i, end=' ')


(arbol, personas) = list(map(int, input().split()))
arbolpos = list(map(int, input().split()))
dic = {}
for i in arbolpos:
	dic[i] = 0
num = 0
x = 0
distancia = 1
res = []
while len(res) < personas:
	node = arbolpos[x]
	if node - 1 not in dic:
		res.append(node - 1)
		arbolpos.append(node - 1)
		dic[node - 1] = dic[node] + 1
		num += dic[node - 1]
	if len(res) == personas:
		break
	if node + 1 not in dic:
		res.append(node + 1)
		arbolpos.append(node + 1)
		dic[node + 1] = dic[node] + 1
		num += dic[node + 1]
	x += 1
print(num)
for i in res:
	print(i, end=' ')


from sys import stdin, stdout
(n, m) = map(int, stdin.readline().split())
treepos = list(map(int, stdin.readline().split()))
treepos.sort()
treespaces = []
spacecounts = {}
for i in range(n - 1):
	spaces = treepos[i + 1] - treepos[i] - 1
	if spaces:
		spacecounts[spaces] = spacecounts.setdefault(spaces, 0) + 1
		treespaces.append((spaces, treepos[i], treepos[i + 1]))
treespaces.sort()
treespaces.append((-1, treepos[-1], treepos[0]))
people = []
total = 0
(dist, i, c, count) = (0, 0, len(treespaces), 0)
while count < m:
	dist += 1
	for j in range(i, c):
		(a, b) = (treespaces[j][1] + dist, treespaces[j][2] - dist)
		people.append(a)
		if a != b:
			total += 2 * dist
			people.append(b)
			count += 2
			if a + 1 == b:
				i = j + 1
		else:
			total += dist
			count += 1
			i = j + 1
rem = count - m
total -= dist * rem
stdout.write('{}\n'.format(total))
stdout.write(' '.join(map(str, people[0:m])))


import string
from collections import defaultdict, Counter
from math import sqrt, log10, log2, log, gcd, ceil, floor, factorial
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations_with_replacement
import sys, io, os
input = sys.stdin.readline
sys.setrecursionlimit(10000)
mod = int(pow(10, 7) + 9)
inf = float('inf')

def get_list():
	return [int(i) for i in input().split()]

def yn(a):
	print('YES' if a else 'NO', flush=False)
t = 1

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
for i in range(t):
	(n, m) = get_list()
	y = get_list()
	seta = SortedList(y)
	yset = set(y)
	occupied = set(y)
	res = 0
	dist = 1
	while len(occupied) < n + m:
		removethem = []
		for j in seta:
			prevres = res
			if j - dist not in occupied:
				occupied.add(j - dist)
				res += dist
			if len(occupied) == n + m:
				break
			if j + dist not in occupied:
				occupied.add(j + dist)
				res += dist
			if len(occupied) == n + m:
				break
			if prevres == res:
				removethem.append(j)
		for i in removethem:
			seta.remove(i)
		dist += 1
	answer = [i for i in occupied if i not in yset]
	print(res)
	print(*answer)


import heapq
(n, m) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
u = set()
for x in a:
	u.add(x)
q = []

def push(d, x, y):
	if y not in u:
		u.add(y)
		heapq.heappush(q, (d, x, y))
for x in a:
	push(1, x, x - 1)
	push(1, x, x + 1)
ans = 0
b = []
for _ in range(m):
	(d, x, y) = heapq.heappop(q)
	ans += d
	b.append(str(y))
	push(d + 1, x, y - 1)
	push(d + 1, x, y + 1)
print(ans)
print(' '.join(b))


import os
import sys
from io import BytesIO, IOBase
from collections import deque, defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))

def bfs(m):
	to_visit = deque()
	visited = defaultdict(int)
	people = []
	for x in xx:
		to_visit.append((0, x))
		visited[x] = 1
	res = 0
	while True:
		(d, x) = to_visit.popleft()
		for y in [x - 1, x + 1]:
			if not visited[y]:
				res += d + 1
				to_visit.append((d + 1, y))
				people.append(y)
				visited[y] = 1
			if len(people) == m:
				return (people, res)
(n, m) = rl()
xx = rl()
(people, res) = bfs(m)
print(res)
print(' '.join([str(y) for y in people]))


(nsap, nhum) = map(int, input().split())
ls = list(map(int, input().split()))
sls = set(ls)
candidates = set()
for e in ls:
	if e + 1 not in sls:
		candidates.add(e + 1)
	if e - 1 not in sls:
		candidates.add(e - 1)
level = 1
totdist = 0
res = set()
while len(res) + len(candidates) <= nhum:
	totdist += level * len(candidates)
	level += 1
	for e in candidates:
		res.add(e)
	cand2 = set()
	for e in candidates:
		for dx in (-1, 1):
			if e + dx not in res and e + dx not in sls:
				cand2.add(e + dx)
	candidates = cand2
for i in range(nhum - len(res)):
	res.add(candidates.pop())
	totdist += level
print(totdist)
for e in res:
	print(e, end=' ')


from bisect import bisect_left, bisect_right
from typing import List
import collections
import bisect
import itertools
import functools
from fractions import gcd
import heapq
from math import ceil, sqrt, floor
import sys
sys.setrecursionlimit(50000)
import collections
from collections import defaultdict, deque
import collections
import bisect
from collections import defaultdict, deque
import collections
(n, m) = list(map(int, input().split()))
xs = list(map(int, input().split()))
dic = {}
for x in xs:
	dic[x] = (x, x)
merged_intervals = []
for (k, v) in dic.items():
	if k - 1 not in dic:
		j = k
		while j + 1 in dic:
			j += 1
		merged_intervals.append((k, j))
merged_intervals.sort()
spaces = []
for i in range(len(merged_intervals) - 1):
	dist = merged_intervals[i + 1][0] - merged_intervals[i][1] - 1
	spaces.append(dist)
total_dist = 0
current_dist = 1
num = 0
ys = []
valid_indices = {i for i in range(len(spaces))}
invalid_indices = set()
while num < m:
	for i in valid_indices:
		if num >= m:
			break
		avail = min(2, spaces[i], m - num)
		num += avail
		total_dist += current_dist * avail
		if avail >= 1:
			ys.append(merged_intervals[i][1] + current_dist)
		if avail >= 2:
			ys.append(merged_intervals[i + 1][0] - current_dist)
		spaces[i] -= avail
		if spaces[i] == 0:
			invalid_indices.add(i)
	if num < m:
		total_dist += current_dist
		ys.append(merged_intervals[0][0] - current_dist)
		num += 1
	if num < m:
		total_dist += current_dist
		ys.append(merged_intervals[-1][1] + current_dist)
		num += 1
	for invalid in invalid_indices:
		valid_indices.remove(invalid)
	if invalid_indices:
		invalid_indices.clear()
	current_dist += 1
print(total_dist)
print(' '.join((str(c) for c in ys)))


(n, m) = [int(x) for x in input().split()]
a = list(sorted([int(x) for x in input().split()]))
b = [a[i] - a[i - 1] - 1 for i in range(1, n)]
c = set()
for i in range(n - 1):
	if b[i] != 0:
		c.add(i)
res = []
su = 0
x = 1
while m != 0:
	if m > 2:
		res.extend([a[0] - x, a[-1] + x])
		su += 2 * x
		m -= 2
		tmp = set()
		for i in c:
			if m > 1:
				if b[i] > 2:
					m -= 2
					b[i] -= 2
					su += 2 * x
					tmp.add(i)
					res.extend([a[i] + x, a[i + 1] - x])
				elif b[i] == 2:
					m -= 2
					su += 2 * x
					b[i] = 0
					res.extend([a[i] + x, a[i + 1] - x])
				else:
					m -= 1
					su += x
					b[i] = 0
					res.append(a[i] + x)
			else:
				m = 0
				res.append(a[i] + x)
				su += x
			if m == 0:
				break
		if m == 0:
			continue
		c = tmp | set()
	elif m == 2:
		res.extend([a[0] - x, a[-1] + x])
		m = 0
		su += 2 * x
	else:
		res.append(a[0] - x)
		m = 0
		su += x
	x += 1
print(su)
print(*res)


import heapq
(n, m) = map(int, input().split())
s = [int(x) for x in input().split()]
s.append(-2 * 10 ** 9)
s.append(2 * 10 ** 9)
kk = dict()
for i in range(0, len(s)):
	kk[s[i]] = 1
s.sort()
q = []
heapq.heapify(q)
for i in range(1, len(s) - 1):
	d1 = s[i] - s[i - 1] - 1
	d2 = s[i + 1] - s[i] - 1
	lf_cap = d1 // 2
	rg_cap = d2 // 2
	if d1 % 2 != 0:
		lf_cap += 1
	t2 = 0
	t3 = 0
	if rg_cap == 0:
		t3 = 10 ** 9
	if lf_cap == 0:
		t2 = 10 ** 9
	heapq.heappush(q, [min(t3, t2) + 1, s[i], t2, t3, lf_cap, rg_cap])
ans = []
tot = 0
while m > 0:
	t = heapq.heappop(q)
	if t[2] + 1 == t[0] and m > 0:
		ans.append(t[1] - t[0])
		t[2] += 1
		tot += t[0]
		m -= 1
	if t[3] + 1 == t[0] and m > 0:
		ans.append(t[1] + t[0])
		t[3] += 1
		tot += t[0]
		m -= 1
	if t[5] == t[3]:
		t[3] = 10 ** 9
	if t[4] == t[2]:
		t[2] = 10 ** 9
	t[0] = min(t[2], t[3]) + 1
	heapq.heappush(q, t)
print(tot)
print(*ans)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
ii = lambda : int(input())
kk = lambda : map(int, input().split())
ll = lambda : list(kk())
(n, m) = kk()
ls = ll()
q = [(l - 1, 1, -1) for l in ls] + [(l + 1, 1, 1) for l in ls]
s = 0
i = -1
vis = set(ls)
res = []
while len(res) < m:
	i += 1
	if q[i][0] in vis:
		continue
	vis.add(q[i][0])
	res.append(q[i][0])
	s += q[i][1]
	q.append((q[i][0] + q[i][2], q[i][1] + 1, q[i][2]))
print(s)
print(*res)


def inp(dtype=str, strip=True):
	s = input()
	res = [dtype(p) for p in s.split()]
	res = res[0] if len(res) == 1 and strip else res
	return res

def problem1():
	t = inp(int)
	for _ in range(t):
		(h, m) = inp(int)
		print((23 - h) * 60 + (60 - m))

def problem2():
	t = inp(int)
	for _ in range(t):
		(n, k) = inp(int)
		res = n // k * k + min(n % k, k // 2)
		print(res)

def problem3():
	n = inp(int)
	f = inp(int, strip=False)
	f = [ch - 1 for ch in f]
	g = [-1 for _ in range(n)]
	for (i, ch) in enumerate(f):
		if ch >= 0:
			g[ch] = i
	gave = set([i for i in range(n) if f[i] >= 0 and g[i] == -1])
	received = set([i for i in range(n) if f[i] == -1 and g[i] >= 0])
	neither = set([i for i in range(n) if f[i] == -1 and g[i] == -1])
	while len(neither):
		if len(received):
			i = received.pop()
		else:
			i = neither.pop()
			gave.add(i)
		j = neither.pop()
		received.add(j)
		f[i] = j
	while len(received):
		i = received.pop()
		j = gave.pop()
		f[i] = j
	f = [ch + 1 for ch in f]
	print(' '.join([str(ch) for ch in f]))

def problem4():
	max_m = 10 ** 6
	(n, m) = inp(int)
	x = inp(int, strip=False)
	x = sorted(x)
	empty = [(0, 0) for _ in range(n + 1)]
	for i in range(1, n):
		empty[i] = (x[i] - x[i - 1] - 1, i)
	empty[0] = (max_m, 0)
	empty[-1] = (max_m, n)
	empty = sorted(empty, key=lambda tup: tup[0])
	cur_dist = 1
	start = 0
	while empty[start][0] == 0:
		start += 1
	j = 0
	y = [0 for _ in range(m)]
	p = start
	res = 0
	while j < m:
		(num, i) = empty[p]
		res += cur_dist
		if i == 0:
			num -= 1
			y[j] = x[i] - cur_dist
			j += 1
		elif i == n:
			num -= 1
			y[j] = x[i - 1] + cur_dist
			j += 1
		else:
			num -= 1
			y[j] = x[i - 1] + cur_dist
			j += 1
			if j < m and num > 0:
				num -= 1
				y[j] = x[i] - cur_dist
				j += 1
				res += cur_dist
		if num == 0:
			start += 1
		empty[p] = (num, i)
		p += 1
		if p == n + 1:
			cur_dist += 1
			p = start
	print(res)
	print(' '.join([str(k) for k in y]))

def problem5():
	pass
problem4()


def arr_inp():
	return [int(x) for x in stdin.readline().split()]

def bfs():
	global m
	(ans, queue, dis) = ([], deque([]), 0)
	for i in a:
		visit[i] = 1
		queue.append(i)
	while queue:
		s = queue.popleft()
		for i in [s - 1, s + 1]:
			if m:
				if visit[i] == 0:
					queue.append(i)
					ans.append(i)
					m -= 1
					visit[i] = 1
			else:
				queue = deque([])
				break
	return ans
from sys import stdin
from collections import defaultdict, deque
from bisect import *
(n, m) = arr_inp()
(a, visit, ans) = (sorted(arr_inp()), defaultdict(int), 0)
arr = bfs()
for i in arr:
	ix = bisect_right(a, i)
	if ix == 0:
		ans += abs(a[0] - i)
	elif ix == n:
		ans += abs(a[-1] - i)
	else:
		ans += min(abs(a[ix - 1] - i), abs(a[ix] - i))
print(ans)
print(*arr)


from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline

def factors(n):
	return sorted(list(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split(' ')]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n').split(' ')]

def li3():
	return [int(i) for i in input().rstrip('\n')]
(n, m) = li()
l = sorted(li())
cnt = Counter(l)
temp = set(l)
ans = 0
leftcounter = deque()
for i in range(n):
	if cnt[l[i] - 1] == 0:
		cnt[l[i] - 1] = 1
		ans += 1
		m -= 1
		leftcounter.append([l[i] - 2, 2, -1])
		if not m:
			break
	if cnt[l[i] + 1] == 0:
		cnt[l[i] + 1] = 1
		ans += 1
		m -= 1
		leftcounter.append([l[i] + 2, 2, 1])
		if not m:
			break
while m:
	(curr, steps, change) = leftcounter.popleft()
	if curr not in cnt:
		cnt[curr] = 1
		ans += steps
		m -= 1
	if curr + change not in cnt:
		leftcounter.append([curr + change, steps + 1, change])
print(ans)
for i in cnt:
	if i not in temp:
		print(i, end=' ')
print()


from sys import stdin
from collections import defaultdict, deque

def bfs():
	visited = dict()
	myq = deque()
	for i in arr:
		visited[i] = True
		myq.append(i)
	cost = 0
	ans = []
	dist = 1
	count = m
	while len(myq) > 0 and count > 0:
		temp = deque()
		while len(myq) > 0 and count > 0:
			node = myq.popleft()
			if count > 0 and node + 1 not in visited:
				temp.append(node + 1)
				visited[node + 1] = True
				cost += dist
				ans.append(node + 1)
				count -= 1
			if count > 0 and node - 1 not in visited:
				temp.append(node - 1)
				visited[node - 1] = True
				cost += dist
				count -= 1
				ans.append(node - 1)
		myq = temp
		dist += 1
	return (cost, ans)
(n, m) = list(map(int, stdin.readline().split()))
arr = list(map(int, stdin.readline().split()))
(cost, ans) = bfs()
print(cost)
print(*ans)


from collections import deque
(n, m) = map(int, input().split())
x = list(map(int, input().split()))
q = deque()
d = {}
for i in range(len(x)):
	q.append(x[i])
	d[x[i]] = 0
vertices = []
count = 0
ans = 0
while count < m:
	t = q.popleft()
	if t - 1 not in d:
		vertices.append(t - 1)
		d[t - 1] = d[t] + 1
		ans = ans + d[t - 1]
		q.append(t - 1)
		count = count + 1
	if count == m:
		break
	if t + 1 not in d:
		vertices.append(t + 1)
		d[t + 1] = d[t] + 1
		ans = ans + d[t + 1]
		q.append(t + 1)
		count = count + 1
print(ans)
for v in vertices:
	print(v, end=' ')


from collections import deque
(n, m) = map(int, input().split())
x = list(map(int, input().split()))
used = set()
for i in range(n):
	used.add(x[i])
ans = 0
dq = deque()
for i in range(n):
	dq.append([0, x[i]])
y = []
while dq:
	(d, p) = dq.popleft()
	if d == 0:
		if not p - 1 in used:
			dq.append([1, p - 1])
		if not p + 1 in used:
			dq.append([1, p + 1])
	else:
		if not p in used:
			used.add(p)
			ans += d
			y.append(p)
			if len(y) >= m:
				break
		if not p + 1 in used:
			dq.append([d + 1, p + 1])
		if not p - 1 in used:
			dq.append([d + 1, p - 1])
print(ans)
print(*y)


(n, m) = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
d = {}
for i in x:
	d[i] = 1
ans = 0
y = []
i = 0
while len(y) < m:
	if x[i] - 1 not in d:
		ans += d[x[i]]
		y.append(x[i] - 1)
		x.append(x[i] - 1)
		d[x[i] - 1] = d[x[i]] + 1
	if len(y) == m:
		break
	if x[i] + 1 not in d:
		ans += d[x[i]]
		y.append(x[i] + 1)
		x.append(x[i] + 1)
		d[x[i] + 1] = d[x[i]] + 1
	i += 1
print(ans)
print(*y)


import sys
import math
from collections import defaultdict, Counter
import bisect
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, m) = map(int, input().split())
x = [-2 * 10 ** 9] + list(map(int, input().split()))
x.sort()
x.append(2 * 10 ** 9)
l = []
for j in range(1, n + 2):
	l.append(x[j] - x[j - 1] - 1)
l.sort()
l1 = len(l)
ind = 1
ans = 0
while True:
	cur = l1 - bisect.bisect_left(l, ind)
	if cur >= m:
		ans += (ind + 1) // 2 * m
		break
	else:
		m -= cur
		ans += (ind + 1) // 2 * cur
		prev = cur
		cur = l1 - bisect.bisect_left(l, ind + 1) - 2
		if cur >= m:
			ans += (ind + 1) // 2 * m
			m += prev
			break
		else:
			m -= cur
			ans += (ind + 1) // 2 * cur
	ind += 2
print(ans)
final = set()
ind = (ind + 1) // 2
for j in range(1, n + 1):
	final.update(range(x[j] - 1, max(x[j] - ind, x[j - 1]), -1))
	final.update(range(x[j] + 1, min(x[j] + ind, x[j + 1])))
	if m:
		if x[j] - x[j - 1] - 1 >= 2 * ind - 1 and x[j] - ind not in final:
			final.add(x[j] - ind)
			m -= 1
		if m:
			if x[j + 1] - x[j] - 1 >= 2 * ind - 1:
				final.add(x[j] + ind)
				m -= 1
print(*final)


import sys
import collections
from collections import Counter, deque
import itertools
import math
import timeit

def sieve(n):
	if n < 2:
		return list()
	prime = [True for _ in range(n + 1)]
	p = 3
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 2
	r = [2]
	for p in range(3, n + 1, 2):
		if prime[p]:
			r.append(p)
	return r

def divs(n, start=1):
	divisors = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				divisors.append(i)
			else:
				divisors.extend([i, n // i])
	return divisors

def divn(n, primes):
	divs_number = 1
	for i in primes:
		if n == 1:
			return divs_number
		t = 1
		while n % i == 0:
			t += 1
			n //= i
		divs_number *= t

def flin(d, x, default=-1):
	left = right = -1
	for i in range(len(d)):
		if d[i] == x:
			if left == -1:
				left = i
			right = i
	if left == -1:
		return (default, default)
	else:
		return (left, right)

def ceil(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def prr(a, sep=' '):
	print(sep.join(map(str, a)))

def dd():
	return collections.defaultdict(int)

def ddl():
	return collections.defaultdict(list)
t = 1
for _ in range(t):
	(n, k) = mi()
	d = li()
	used = set(d)
	left = d[:]
	right = d[:]
	res = []
	s = 0
	c = 1
	while len(res) < k:
		nl = []
		nr = []
		j = 0
		while len(res) < k and j < len(left):
			if left[j] - 1 not in used:
				s += c
				res.append(left[j] - 1)
				used.add(left[j] - 1)
				nl.append(left[j] - 1)
			j += 1
		j = 0
		while len(res) < k and j < len(right):
			if right[j] + 1 not in used:
				s += c
				res.append(right[j] + 1)
				used.add(right[j] + 1)
				nr.append(right[j] + 1)
			j += 1
		left = nl
		right = nr
		c += 1
	print(s)
	prr(res)


import sys
input = sys.stdin.readline
from collections import deque
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
Q = deque()
for x in a:
	Q.append((x, 1, 0))
	Q.append((x, -1, 0))
visit = set(a)
ans = 0
while len(visit) < m + n:
	(x, dir, dist) = Q.popleft()
	nx = x + dir
	ndist = dist + 1
	if nx not in visit:
		visit.add(nx)
		Q.append((nx, dir, ndist))
		ans += ndist
visit = visit - set(a)
print(ans)
print(*visit)


from collections import deque
qu = deque([])
(n, m) = map(int, input().split())
dist = {}
ls = list(map(int, input().split()))
for i in ls:
	dist[i] = 0
	qu.append(i)
res = set()
ans = 0
flag = True
while True:
	x = qu.popleft()
	if x - 1 not in dist:
		qu.append(x - 1)
		res.add(x - 1)
		dist[x - 1] = dist[x] + 1
		ans += dist[x - 1]
	if len(res) == m:
		break
	if x + 1 not in dist:
		qu.append(x + 1)
		res.add(x + 1)
		dist[x + 1] = dist[x] + 1
		ans += dist[x + 1]
	if len(res) == m:
		break
print(ans)
print(' '.join(map(str, res)))


(n, m) = map(int, input().split())
x = list(map(int, input().split()))
used = set(x)
cost = 0
ans = []
from collections import deque
q = deque()
for tree in x:
	q.append((tree - 1, 1))
	q.append((tree + 1, 1))
while m > 0:
	(pos, d) = q.popleft()
	if pos in used:
		continue
	used.add(pos)
	cost += d
	m -= 1
	ans.append(pos)
	q.append((pos + 1, d + 1))
	q.append((pos - 1, d + 1))
print(cost)
print(*ans)