This is the hard version of the problem. The difference between versions is the constraints on $n$ and $a_i$. You can make hacks only if all versions of the problem are solved.

First, Aoi came up with the following idea for the competitive programming problem:

Yuzu is a girl who collecting candies. Originally, she has $x$ candies. There are also $n$ enemies numbered with integers from $1$ to $n$. Enemy $i$ has $a_i$ candies.

Yuzu is going to determine a permutation $P$. A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $\{2,3,1,5,4\}$ is a permutation, but $\{1,2,2\}$ is not a permutation ($2$ appears twice in the array) and $\{1,3,4\}$ is also not a permutation (because $n=3$ but there is the number $4$ in the array).

After that, she will do $n$ duels with the enemies with the following rules:

  If Yuzu has equal or more number of candies than enemy $P_i$, she wins the duel and gets $1$ candy. Otherwise, she loses the duel and gets nothing.  The candy which Yuzu gets will be used in the next duels. 

Yuzu wants to win all duels. How many valid permutations $P$ exist?

This problem was easy and wasn't interesting for Akari, who is a friend of Aoi. And Akari made the following problem from the above idea:

Let's define $f(x)$ as the number of valid permutations for the integer $x$.

You are given $n$, $a$ and a prime number $p \le n$. Let's call a positive integer $x$ good, if the value $f(x)$ is not divisible by $p$. Find all good integers $x$.

Your task is to solve this problem made by Akari.


-----Input-----

The first line contains two integers $n$, $p$ $(2 \le p \le n \le 10^5)$. It is guaranteed, that the number $p$ is prime (it has exactly two divisors $1$ and $p$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le 10^9)$.


-----Output-----

In the first line, print the number of good integers $x$.

In the second line, output all good integers $x$ in the ascending order.

It is guaranteed that the number of good integers $x$ does not exceed $10^5$.


-----Examples-----
Input
3 2
3 4 5

Output
1
3

Input
4 3
2 3 5 6

Output
2
3 4

Input
4 3
9 1 1 1

Output
0


Input
3 2
1000000000 1 999999999

Output
1
999999998



-----Note-----

In the first test, $p=2$.

  If $x \le 2$, there are no valid permutations for Yuzu. So $f(x)=0$ for all $x \le 2$. The number $0$ is divisible by $2$, so all integers $x \leq 2$ are not good.  If $x = 3$, $\{1,2,3\}$ is the only valid permutation for Yuzu. So $f(3)=1$, so the number $3$ is good.  If $x = 4$, $\{1,2,3\} , \{1,3,2\} , \{2,1,3\} , \{2,3,1\}$ are all valid permutations for Yuzu. So $f(4)=4$, so the number $4$ is not good.  If $x \ge 5$, all $6$ permutations are valid for Yuzu. So $f(x)=6$ for all $x \ge 5$, so all integers $x \ge 5$ are not good. 

So, the only good number is $3$.

In the third test, for all positive integers $x$ the value $f(x)$ is divisible by $p = 3$.

Source: codeforces | Difficulty: HARD
Tags: Sorting

Combinatorics

Number theory

Dynamic programming

Mathematics


Solutions:
(n, p) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
smalls = [l[i] - i for i in range(n)]
tols = [l[i] - i + p - 1 for i in range(p - 1, n)]
smol = max(smalls)
tol = min(tols)
out = list(range(smol, tol))
print(len(out))
print(' '.join(map(str, out)))


def smallest_winner(matrix, starting_x, x):
	for m in matrix:
		if m > x:
			starting_x += m - x
			x += m - x
		x += 1
	return starting_x

def biggest_winner(matrix, p, maxi):
	for i in range(len(matrix)):
		if i + p - 1 >= len(matrix):
			break
		maxi = min(maxi, matrix[i + p - 1] - i)
	return maxi
(n, p) = map(int, input().split())
matrix = sorted(list(map(int, input().split())))
res = [i for i in range(smallest_winner(matrix, 1, 1), biggest_winner(matrix, p, matrix[-1]))]
print(len(res))
print(' '.join(map(str, res)))


import sys
lines = sys.stdin.readlines()
(n, p) = map(int, lines[0].strip().split(' '))
arr = list(map(int, lines[1].strip().split(' ')))
arr.sort()
counter = {}
for a in arr:
	if a not in counter:
		counter[a] = 0
	counter[a] += 1
lower = max(arr[-1] - n + 1, 1)
(a, b, c, d) = (lower - 1, -1, -1, arr[-1] + 1)

def check(val):
	pt = 0
	cnt = 0
	while pt < n and arr[pt] <= val:
		cnt += 1
		pt += 1
	if cnt >= p:
		return 1
	while cnt > 0:
		val += 1
		cnt -= 1
		if val in counter:
			cnt += counter[val]
		if cnt >= p:
			return 1
		if val >= arr[-1]:
			break
	if cnt <= 0 or val < arr[-1]:
		return -1
	else:
		return 0
exist = False
while a < d - 1:
	mid = (a + d) // 2
	res = check(mid)
	if res == 1:
		d = mid
	elif res == -1:
		a = mid
	else:
		exist = True
		break
if exist:
	b = mid
	c = mid
	while a < b - 1:
		mid = (a + b) // 2
		res = check(mid)
		if res == 0:
			b = mid
		else:
			a = mid
	while c < d - 1:
		mid = (c + d) // 2
		if check(mid) == 1:
			d = mid
		else:
			c = mid
if exist:
	print(c - b + 1)
	print(' '.join(map(str, range(b, c + 1))))
else:
	print(0)
	print()


import sys
import collections

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

def split_input():
	return [int(i) for i in input().split()]
(n, p) = split_input()
a = split_input()
start = max(a) - n + 1
x = [0 for i in range(n)]
for i in a:
	ind = i - start
	if ind <= 0:
		x[0] += 1
	else:
		x[ind] += 1
for i in range(1, n):
	x[i] += x[i - 1]
zero_ind = -1
for i in range(n):
	zero_ind = max(i - x[i], zero_ind)
s = set()
for i in range(zero_ind + 1, n):
	if x[i] >= p:
		s.add((i + start - x[i]) % p)
ans = []
for i in range(zero_ind + 1, p):
	if (i + start) % p not in s:
		ans.append(i + start)
print(len(ans))
print(*ans, sep=' ')


def smallest_winner(matrix):
	starting_x = 1
	x = 1
	for m in matrix:
		if m > x:
			starting_x += m - x
			x += m - x
		x += 1
	return starting_x

def biggest_winner(matrix, p):
	maxi = matrix[-1]
	for i in range(len(matrix)):
		if i + p - 1 >= len(matrix):
			break
		temp = matrix[i + p - 1] - i
		maxi = min(maxi, temp)
	return maxi

def check_multiple(matrix):
	count = 0
	maxi = 0
	for i in range(1, len(matrix)):
		if matrix[i] == matrix[i - 1]:
			count += 1
		else:
			count = 1
		maxi = max(maxi, count)
	return maxi

def solve(n, p, matrix):
	matrix = sorted(matrix)
	min_x = smallest_winner(matrix)
	max_x = biggest_winner(matrix, p) - 1
	return [i for i in range(min_x, max_x + 1)]
(n, p) = map(int, input().split())
matrix = map(int, input().split())
res = solve(n, p, matrix)
print(len(res))
print(' '.join(map(str, res)))


lis = input().split()
(n, p) = (int(lis[0]), int(lis[1]))
lis = input().split()
a = [0] * n
for i in range(n):
	a[i] = int(lis[i])
a.sort()
xminn = a[0]
for i in range(1, n):
	xminn = max(a[i] - i, xminn)
for i in range(n):
	a[i] = min(xminn - a[i] + 1 + i, i + 1)
lenn = n
i = p
while i <= n:
	lenn = min(i - a[i - 1], lenn)
	i += p
if lenn == 0:
	print(0)
else:
	notAllowed = [False] * lenn
	for i in range(n):
		uplim = min(a[i] + lenn - 1, i + 1)
		val = ((a[i] - 1) // p + 1) * p
		if val <= uplim:
			notAllowed[val - a[i]] = True
	good = []
	for i in range(lenn):
		if not notAllowed[i]:
			good.append(xminn + i)
	print(len(good))
	for i in good:
		print(i, end=' ')
	print()


def solution(n, a, p):
	result = []
	r = []
	a.sort()
	for i in range(n):
		r.append(-a[i] + i + 1)
	remainder = []
	for i in range(p):
		remainder.append(0)
	for i in range(p - 1, n):
		n_a_re = (p - r[i]) % p
		remainder[n_a_re] += 1
	min_x = 1 - n + a[n - 1]
	for i in range(2, n + 1):
		if i - n + a[n - i] > min_x:
			min_x = i - n + a[n - i]
	result += get_x(min_x, a[p - 1], remainder, p, n, p - 2)
	return result

def get_x(start, end, remainder, p, n, id):
	v1 = start // p
	r1 = start % p
	v2 = end // p
	r2 = end % p
	arr = []
	s_id = -1
	e_id = -1
	if end > start:
		for i in range(len(remainder)):
			if remainder[i] == 0:
				arr.append(v1 * p + i)
				if i >= r1 and s_id == -1:
					s_id = len(arr) - 1
				if i >= r2 and e_id == -1:
					e_id = len(arr) - 1
		period = len(arr)
		for _ in range((v2 - v1) * period):
			arr.append(arr[-period] + p)
		if s_id == -1:
			s_id = period
		if e_id == -1:
			e_id = period
		remainder[(p + end - id - 2) % p] -= 1
		return arr[s_id:len(arr) - period + e_id]
	else:
		remainder[(p + end - id - 2) % p] -= 1
		return []
num = input()
num = num.split(' ')
n = int(num[0])
p = int(num[1])
a = list(map(int, input().split(' ')))
result = solution(n, a, p)
print(len(result))
print(' '.join(list(map(str, result))))


(n, p) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
left = 0
right = 10 ** 9 + 1
while right - left > 1:
	mid = left + (right - left) // 2
	x = mid
	flag = 1
	for i in range(n):
		if a[i] <= x:
			x += 1
		else:
			flag = 0
			break
	if flag:
		right = mid
	else:
		left = mid
ansleft = right
left = 0
right = 10 ** 9 + 1
while right - left > 1:
	mid = left + (right - left) // 2
	x = mid
	flag = 1
	r = 0
	for i in range(n):
		while r < n:
			if a[r] <= x:
				r += 1
			else:
				break
		if r - i >= p:
			flag = 0
			break
		x += 1
	if flag:
		left = mid
	else:
		right = mid
ansright = left
ans = [i for i in range(ansleft, ansright + 1)]
print(len(ans))
print(*ans)


import math
import collections
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect_left as bsl
from bisect import bisect_right as bsr
import heapq as hq
setrecursionlimit(2 ** 20)
t = 1
d = {}

def bin(a, k):
	cnt = bsr(a, k)
	for i in range(n):
		if cnt >= p:
			return True
		cnt -= 1
		k += 1
		if k in d:
			cnt += d[k]
	return False
dp = [1] * 100001
for _ in range(t):
	(n, p) = list(map(int, stdin.readline().rstrip().split()))
	a = list(map(int, stdin.readline().rstrip().split()))
	a.sort()
	for i in range(n):
		a[i] -= i
	mi = max(a)
	for i in range(n):
		a[i] += p - 1
	ma = min(a[p - 1:])
	print(max(ma - mi, 0))
	print(*list(range(mi, ma)))


from sys import stdin, stdout

def asterism(n, p, a):
	res = []
	a.sort()
	l = a[n - 1]
	for i in range(n - 1, -1, -1):
		l = max(a[i], l)
		l -= 1
	l += 1
	minl = l
	if check(bs(minl, a), minl, a, p):
		return res
	h = max(minl, a[n - 1] - 1)
	while l < h:
		m = (l + h + 1) // 2
		idx = bs(m, a)
		if not check(idx, m, a, p):
			l = m
		else:
			h = m - 1
	for i in range(minl, l + 1):
		res.append(i)
	return res

def check(idx, v, a, p):
	for i in range(len(a)):
		if idx + 1 - i >= p:
			return True
		v += 1
		idx += 1
		if idx == len(a):
			break
		while idx < len(a) and a[idx] <= v:
			idx += 1
		idx -= 1
	return False

def bs(v, a):
	l = 0
	h = len(a) - 1
	while l < h:
		m = (l + h + 1) // 2
		if a[m] > v:
			h = m - 1
		else:
			l = m
	return l
(n, p) = map(int, stdin.readline().split())
a = list(map(int, stdin.readline().split()))
res = asterism(n, p, a)
stdout.write(str(len(res)) + '\n')
if len(res) > 0:
	stdout.write(' '.join(map(str, res)) + '\n')


import sys
from collections import defaultdict as dd
from collections import deque
from fractions import Fraction as f
from copy import *
from bisect import *
from heapq import *
from math import *
from itertools import permutations

def eprint(*args):
	print(*args, file=sys.stderr)
zz = 1
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')

def li():
	return [int(x) for x in input().split()]

def gi():
	return [x for x in input().split()]

def fi():
	return int(input())

def si():
	return list(input().rstrip())

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

def gh():
	sys.stdout.flush()

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)

def bo(i):
	return ord(i) - ord('a')
t = 1

def can(l):
	cc = 0
	dif = [0 for i in range(n + 1)]
	w = []
	for i in range(n):
		start = max(0, a[i] - l)
		if a[i] - l >= n:
			return 0
		w.append(a[i] - l)
		dif[start] += 1
		dif[n] -= 1
	for i in range(1, n + 1):
		dif[i] += dif[i - 1]
	ans = 1
	c = 0
	for i in range(n):
		if dif[i] - c <= 0:
			return 0
		if (dif[i] - c) % p == 0 and dif[i] - c >= p:
			return 2
		c += 1
	return 1
while t > 0:
	t -= 1
	(n, p) = mi()
	a = li()
	a.sort()
	l = 1
	r = max(a) + 1
	(ansl, ansr) = (-1, -2)
	while l <= r:
		mid = (l + r) // 2
		z = can(mid)
		if z == 2:
			r = mid - 1
		elif z == 0:
			l = mid + 1
		else:
			ansr = mid
			l = mid + 1
	l = 1
	r = max(a) + 1
	while l <= r:
		mid = (l + r) // 2
		z = can(mid)
		if z == 2:
			r = mid - 1
		elif z == 0:
			l = mid + 1
		else:
			ansl = mid
			r = mid - 1
	print(ansr - ansl + 1)
	for i in range(ansl, ansr + 1):
		print(i, end=' ')


import bisect
import sys
input = sys.stdin.readline
(n, p) = map(int, input().split())
arr1 = list(map(int, input().split()))
arr1 = sorted(arr1)
mins = 0
for i in range(n):
	mins = max(mins, arr1[i] - i)
maxs = arr1[p - 1]
arr2 = [0] * n
for i in range(n):
	arr2[i] = (n - arr1[n - i - 1] - i) % p
arr2 = arr2[::-1]
can = set(range(p))
pos = bisect.bisect_right(arr1, maxs - 1)
for i in range(pos, n):
	can.discard((p - arr2[i]) % p)
ans = []
prev = pos
for x in range(maxs - 1, mins - 1, -1):
	pos = bisect.bisect_right(arr1, x)
	if pos == prev:
		if x % p in can:
			ans.append(x)
	else:
		for i in range(pos, prev):
			can.discard((p - arr2[i]) % p)
		if x % p in can:
			ans.append(x)
	prev = pos
ans = ans[::-1]
print(len(ans))
print(*ans)


def asterism(p, a):
	(n, m, M) = (len(a), 1, max(a) - 1)
	for i in range(n):
		m = max(m, a[i] - i)
	for i in range(n - p + 1):
		M = min(M, a[p + i - 1] - i - 1)
	print(max(0, M - m + 1))
	for i in range(m, M + 1):
		print(i, end=' ')
asterism(int(input().split()[1]), sorted([int(i) for i in input().split()]))


def places(num, v):
	if num >= v + n:
		return 0
	if num < v:
		return n
	return n - (num - v)

def check(num):
	for i in range(n - 1, -1, -1):
		count = max(0, places(b[i], num) - (n - 1 - i))
		if count == 0:
			return True
		if count % p == 0:
			return False
	return False

def check2(num):
	for i in range(n - 1, -1, -1):
		count = max(0, places(b[i], num) - (n - 1 - i))
		if count % p == 0:
			return True
	return False
(n, p) = map(int, input().split())
a = list(map(int, input().split()))
b = sorted(a)
minn = b[0]
maxx = b[-1]
low = 0
high = maxx - 1
while low < high:
	mid = (low + high) // 2
	if check(mid):
		low = mid + 1
	else:
		high = mid - 1
if check(low):
	start = low + 1
else:
	start = low
low = start
high = maxx - 1
while low < high:
	mid = (low + high) // 2
	if not check2(mid):
		low = mid + 1
	else:
		high = mid - 1
if check2(low):
	end = low - 1
else:
	end = low
ans = []
for i in range(start, end + 1):
	ans.append(i)
print(len(ans))
print(*ans)


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
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')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

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

def N():
	return int(input())
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
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa = ifa[::-1]

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def linc(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t > f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rinc(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t < f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def ldec(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t < f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rdec(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t > f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def binfun(x):
	c = 0
	for w in arr:
		c += ceil(w / x)
	return c

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] < self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [(ch, len(list(g))) for (ch, g) in groupby(it)]

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None
t = 1
for i in range(t):
	(n, p) = RL()
	a = RLL()
	a.sort()
	mi = max((a[i] - i for i in range(n)))
	ma = a[-1] - 1
	if mi > ma:
		print(0)
		print()
		exit()
	j = cur = 0
	res = []
	for i in range(mi, ma + n):
		while j < n and a[j] <= i:
			j += 1
			cur += 1
		res.append((i - cur) % p)
	c = Counter()
	ans = []
	for r in range(n):
		c[res[r]] += 1
	if c[mi % p] == 0:
		ans.append(mi)
	r = n
	for x in range(mi + 1, ma + 1):
		c[res[r]] += 1
		c[res[r - n]] -= 1
		if c[x % p] == 0:
			ans.append(x)
		r += 1
	print(len(ans))
	print(*ans)


def ican(a, x):
	k = x
	wr = 0
	for i in range(len(a)):
		if a[i] <= k:
			wr += 1
		else:
			wr -= a[i] - k
			k = a[i]
			if wr < 0:
				return False
			wr += 1
	return True

def bnpleft(a):
	r = max(a)
	l = -1
	while r - l > 1:
		h = (r + l) // 2
		if ican(a, h):
			r = h
		else:
			l = h
	return l

def fa(a, x, p):
	k = x
	wr = 0
	for i in range(len(a)):
		if a[i] <= k:
			wr += 1
		else:
			nk = wr // p * p
			wr -= a[i] - k
			if wr < nk:
				return False
			k = a[i]
			if wr < 0:
				return False
			wr += 1
	if wr >= p:
		return False
	else:
		return True

def bnpr(a, p, left):
	l = left
	r = max(a)
	while r - l > 1:
		h = (r + l) // 2
		if fa(a, h, p):
			l = h
		else:
			r = h
	return l

def solve():
	(n, p) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst.sort()
	ll = bnpleft(lst)
	rr = bnpr(lst, p, ll)
	print(rr - ll)
	for i in range(ll + 1, rr + 1):
		print(i, end=' ')
for i in range(1):
	solve()


def read_list():
	return list(map(int, input().strip().split(' ')))

def print_list(l):
	print(' '.join(map(str, l)))
(n, p) = read_list()
a = read_list()
a.sort()
mi = max((a[i] - i for i in range(n)))
res = []
ll = []
x = mi
now = x
i = 0
dic = [[-1]]
for step in range(n):
	while i < n and now >= a[i]:
		i += 1
	now += 1
	tmp = (i - step) % p
	tmp = (p - tmp) % p
	if step >= tmp:
		dic.append([tmp, step])
dic.pop(0)
for i in range(len(dic) - 1, 0, -1):
	if dic[i][0] <= dic[i - 1][1] - 1:
		dic[i - 1][1] = dic[i][1]
		dic[i - 1][0] = min(dic[i][0], dic[i - 1][0])
		dic.pop(i)
las = 0
for d in dic:
	flag = True
	for i in range(las, d[0]):
		if i >= p - 1:
			flag = False
			break
		res.append(mi + i)
	las = d[1] + 1
	if not flag:
		break
if dic:
	for i in range(dic[-1][-1] + 1, p - 1):
		res.append(mi + i)
print(len(res))
print_list(res)


import sys

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

def solve():
	(n, p) = LI()
	a = LI()
	a.sort()
	ap = [i for i in a[p - 1:]]
	ap = [ap[i] - i for i in range(len(ap))]
	M = min(ap)
	b = [a[i] - i for i in range(n)]
	m = max(b)
	ans = list(range(m, M))
	print(len(ans))
	print(*ans)
	return
solve()


(n, p) = list(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
a.sort()
result = []
_min = 0
for i in range(len(a) - 1, -1, -1):
	if _min <= a[i] - i:
		_min = a[i] - i
_max = a[-1]
for i in range(len(a) - 1, p - 2, -1):
	if _max >= p - 2 - i + a[i]:
		_max = p - 2 - i + a[i]
result = max(_max - _min + 1, 0)
print(result)
if result > 0:
	for i in range(_min, _max + 1):
		print(i, end=' ')


import bisect
(n, p) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
xmin = a[-1] - n + 1
v = []
for x in range(xmin, xmin + n):
	v.append(bisect.bisect(a, x))
mods = [0] * p
mod_shift = 0
mi = n + 1
xs = []
for i in range(len(v) - 1, -1, -1):
	mi = min(mi - 1, v[i])
	mod_shift = (mod_shift + 1) % p
	mods[(mod_shift + v[i]) % p] += 1
	if i < p and mi >= 0 and (mods[mod_shift] == 0):
		xs.append(xmin + i)
print(len(xs))
print(*xs[::-1])


(n, p) = map(int, input().split())
s = sorted(map(int, input().split()))
for i in range(n):
	s[i] -= i
mn = max(s)
for i in range(n):
	s[i] += p - 1
mx = min(s[p - 1:])
ans = [*range(mn, mx)]
print(len(ans))
print(*ans)


(n, p) = map(int, input().split())
a = sorted(map(int, input().split()))
b = []
i = 0
while i < len(a):
	j = i
	while j < len(a) and a[j] == a[i]:
		j += 1
	b.append((a[i], j - i))
	i = j
l = a[-1] - n
r = a[-1]
s = [0] * (r - l + n)
cc = n
ci = r - 1 + n
for i in range(len(b) - 1, -1, -1):
	cj = b[i][0]
	while ci >= cj and ci >= l:
		s[ci - l] = ci - cc
		ci -= 1
	cc -= b[i][1]
while ci >= l:
	s[ci - l] = ci - cc
	ci -= 1
c = [0] * p
for i in range(l, l + n):
	c[s[i - l] % p] += 1
ans = []
for x in range(l, r):
	if c[x % p] == 0:
		ans.append(x)
	c[s[x - l] % p] -= 1
	c[s[x + n - l] % p] += 1
print(len(ans))
print(*ans)


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	from collections import Counter
	input = sys.stdin.readline
	(N, p) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	x0 = -1
	for i in range(N):
		x0 = max(x0, A[i] - i)
	x1 = A[p - 1]
	dic = {}
	i = 0
	for x in range(x0, x0 + 2 * 10 ** 5 + 1):
		while True:
			if i == N - 1:
				break
			if A[i + 1] <= x:
				i += 1
			else:
				break
		dic[x] = i + 1
	ok = x0 - 1
	ng = x1
	mid = (ok + ng) // 2
	while ng - ok > 1:
		x = mid
		flg = 1
		for i in range(N):
			if (dic[x + i] - i) % p == 0:
				flg = 0
				break
		if flg:
			ok = mid
		else:
			ng = mid
		mid = (ok + ng) // 2
	print(ok - x0 + 1)
	X = list(range(x0, ok + 1))
	print(*X)
main()


import math
import sys
input = sys.stdin.readline
(n, p) = list(map(int, input().split()))
a = sorted([int(_) for _ in input().split()])
inf = 10 ** 18
bad = dict()
(low, high) = (1, inf)
opt = [0] * p
for i in range(n):
	j = (i + 1) % p
	if a[i] >= j:
		var = (a[i] - j) % p
		opt[var] = max(opt[var], a[i] - j)
	if j == 0:
		high = min(high, a[i])
	low = max(low, a[i] - i)
for i in range(p):
	cur = opt[i]
	while cur >= low:
		bad[cur] = True
		cur -= p
result = []
for i in range(low, high):
	if bad.get(i, False) == False:
		result.append(i)
print(len(result))
print(' '.join(map(str, result)))


(n, p) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(n):
	a[i] -= i
l = max(a)
for i in range(n):
	a[i] += p - 1
r = min(a[p - 1:])
print(max(r - l, 0))
print(*list(range(l, r)))


import sys
input = sys.stdin.readline
inputr = lambda : sys.stdin.readline().rstrip('\n')
from collections import Counter
(n, p) = map(int, input().split())
A = sorted(map(int, input().split()))
B = sorted(Counter(A).items())
M = max(n, p) + 1
fact = [1] * M
for i in range(2, M):
	fact[i] = fact[i - 1] * i % p
ifact = [1] * M
ifact[p - 1] = pow(fact[p - 1], p - 2, p)
for i in range(p - 1, -1, -1):
	ifact[i - 1] = ifact[i] * i % p
min_pow = x = 1
for (k, v) in B:
	if x < k:
		min_pow += k - x
		x = k
	x += v

def check(x):
	i = 0
	r = 1
	candef = 0
	while True:
		while i < len(B) and x >= B[i][0]:
			candef += B[i][1]
			i += 1
		if i == len(B):
			r *= fact[candef]
			r %= p
			break
		need = B[i][0] - x
		if candef < need:
			r = 0
			break
		r *= fact[candef] * ifact[candef - need]
		r %= p
		candef -= need
		x += need
	return r != 0
lo = min_pow
hi = max(A) + 1
while lo < hi:
	m = (lo + hi) // 2
	if check(m):
		lo = m + 1
	else:
		hi = m
print(hi - min_pow)
print(*range(min_pow, hi))


(n, p) = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
m = max((a[i] - i for i in range(n)))
M = a[p - 1] - 1
ban = [0 for i in range(p)]
ans = []
query = [(a[i] - 1 - i, 1, -100) for i in range(n)]
for x in range(m, M + 1):
	query.append((x, 0, -100))
for i in range(n):
	query.append((a[i], -1, i))
query.sort()
for (val, q, id) in query:
	if q == -1:
		r = (val - id - 1) % p
		ban[r] -= 1
	elif q == 0:
		if ban[val % p] == 0:
			ans.append(val)
	else:
		ban[val % p] += 1
ans.sort()
print(len(ans))
print(*ans)


import copy
con = 10 ** 9 + 7
INF = float('inf')

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

def Binary_Search(N, P, A, dif):
	left = 0
	right = N - 1
	ansleft = dif
	ansright = -INF
	while left <= right:
		mid = (left + right) // 2
		jud = 'Yes'
		B = copy.deepcopy(A)
		B.append(INF)
		for t in range(N):
			B[t] -= mid
		array = [None] * N
		i = 0
		j = 0
		while True:
			if B[j] <= i:
				j += 1
			else:
				if (j - i) % P == 0:
					jud = 'No'
					break
				array[i] = j - i
				i += 1
			if i >= N:
				break
		if jud == 'Yes':
			ansright = max(ansright, dif + mid)
			left = mid + 1
		else:
			right = mid - 1
	return (ansleft, ansright)

def main():
	(N, P) = getlist()
	A = getlist()
	A = sorted(A)
	dif = 0
	for i in range(N):
		dif = max(dif, A[i] - i)
	for i in range(N):
		A[i] -= dif
	(L, R) = Binary_Search(N, P, A, dif)
	if R == -INF:
		print(0)
		print()
	else:
		Xlis = [i for i in range(L, R + 1)]
		print(len(Xlis))
		print(*Xlis)
main()


(n, p) = map(int, input().split())
arr = list(map(int, input().split()))
(l, r) = (0, float('inf'))
arr.sort()
for i in range(len(arr)):
	l = max(l, arr[i] - i)
	if i + 1 >= p:
		r = min(r, arr[i] - i + p - 1)
print(max(0, r - l))
res = []
for i in range(l, r):
	res.append(i)
print(*res)


import sys
input = sys.stdin.readline
(n, p) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
mn = 0
mx = 2000000000000000
for i in range(n):
	d = a[i] - i
	mn = max(d, mn)
	if i >= p - 1:
		d2 = a[i] - i + p - 1
		mx = min(mx, d2)
print(max(mx - mn, 0))
for i in range(mn, mx):
	print(i, end=' ')


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')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

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

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush
from bisect import bisect_right

def main():
	(n, pr) = RL()
	arr = RLL()
	arr.sort()
	mis = [arr[i] - i for i in range(n)]
	up = [arr[i] - i + pr - 1 for i in range(pr - 1, n)]
	res = list(range(max(mis), min(up)))
	print(len(res))
	print(*res)
main()


import sys
input = sys.stdin.readline
(n, p) = map(int, input().split())
A = sorted(map(int, input().split()))
MAX = A[-1]
start = max(A[0], MAX - (n - 1))
S = []
ind = 0
for c in range(start, MAX + 1):
	while ind < n and A[ind] <= c:
		ind += 1
	S.append(ind)
SS = [S[i] - i for i in range(len(S))]
MAX = 10 ** 9
MIN = 0
for i in range(len(S)):
	if SS[i] <= 0:
		MIN = max(MIN, 1 - SS[i])
	elif p - 1 - S[i] + i < i:
		MAX = min(MAX, p - 1 - S[i] + i)
ANS = []
for i in range(MIN, MAX + 1):
	ANS.append(start + i)
print(len(ANS))
print(*ANS)


(n, p) = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 0
ansls = []
mx = max(a)
mn = max([a[i] - i for i in range(n)])
ansmx = -1
for j in range(p - 1, n)[::-1]:
	ansmx = max(ansmx, n - max(mn, a[j]) + mn - (n - j - 1))
while ansmx < p:
	ans += 1
	ansls.append(mn)
	mn += 1
	ansmx += 1
print(ans)
print(*ansls)


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque, defaultdict
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000000 + 7
mod2 = 998244353
(n, p) = M()
a = sorted(L())
for i in range(n):
	a[i] -= i
m1 = max(a)
for i in range(n):
	a[i] += p - 1
m2 = min(a[p - 1:])
print(max(0, m2 - m1))
print(*list(range(m1, m2)))


def solve(n, p, array):
	array.sort()
	array1 = [i + 1 - array[i] for i in range(n)]
	m = min(array1)
	min_x = 1 - min(m, 0)
	valid = [1 for i in range(n)]
	max_v = n - 1
	for i in range(n):
		a = array1[i] + min_x
		if (i + 1) % p == 0:
			max_v = min(array[i] - min_x - 1, max_v)
		if a <= i + 1:
			cur = -a % p
			end = min(i + 1 - a, max_v)
			while cur <= end:
				valid[cur] = 0
				cur += p
	res = []
	for i in range(max_v + 1):
		if valid[i]:
			res.append(min_x + i)
	print(len(res))
	print(*res)
(n, p) = [int(s) for s in input().split()]
array = [int(s) for s in input().split()]
solve(n, p, array)


import sys
input = sys.stdin.readline
import bisect
(n, p) = map(int, input().split())
a = [int(i) for i in input().split() if i != '\n']
a.sort()
(j, k) = (a[0], a[0])
for i in range(1, n):
	if a[i] - k > 1:
		j += a[i] - k - 1
		k = a[i]
	else:
		k += 1
unique = [1]
for i in range(1, n):
	unique.append(unique[-1] + 1)
mina = a[-1]
for i in range(n):
	bis = bisect.bisect(unique, i + p)
	mina = min(mina, a[bis - 1] - i)
	if bis == n:
		break
out = list(range(j, mina))
sys.stdout.write(str(len(out)) + '\n')
out = ' '.join(map(str, out))
sys.stdout.write(out)


from bisect import bisect_right as br
import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

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

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

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

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]
(n, p) = MI()
aa = LI()
aa.sort()

def low(x):
	for i in range(n):
		if br(aa, i + x) - i < 1:
			return False
	return True
l = min(aa) - 1
r = max(aa) + 1
while l + 1 < r:
	x = (l + r) // 2
	if low(x):
		r = x
	else:
		l = x
mn = r

def high(x):
	for i in range(n):
		if br(aa, i + x) - i >= p:
			return False
	return True
l = mn - 1
r = max(aa) + 1
while l + 1 < r:
	x = (l + r) // 2
	if high(x):
		l = x
	else:
		r = x
mx = l
ans = list(range(mn, mx + 1))
print(len(ans))
print(*ans)


from sys import stdin, gettrace
from collections import Counter
from functools import reduce
from itertools import accumulate
if gettrace():
	inputi = input
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def main():
	(n, p) = map(int, inputi().split())
	aa = [int(a) for a in inputi().split()]
	aa.sort()
	minx = max([a - i for (i, a) in enumerate(aa)])
	bi = minx
	bb = []
	for (i, a) in enumerate(aa):
		if a > bi:
			bb += [i] * (a - bi)
			bi = a
	bb += [n] * (2 * n - len(bb))
	i = 0
	t = max(aa)
	while i < n and t >= minx:
		c = bb[i + t - minx] - i
		if c < p:
			i += 1
		else:
			t -= 1
	print(t - minx + 1)
	print(' '.join(map(str, range(minx, t + 1))))
main()


import collections
import bisect
(n, p) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()
memo = collections.deque()
(minx, maxx) = (0, 9999999999999)
for i in reversed(a):
	minx = max(minx - 1, i)
	if len(memo) == p - 1:
		maxx = min(maxx - 1, memo[0] - 1)
		memo.popleft()
	memo.append(i)
if minx > maxx:
	print(0)
else:
	print(maxx - minx + 1)
	for i in range(minx, maxx + 1):
		print(i, end=' ')


import sys
import math
from math import factorial, inf, gcd, sqrt
from heapq import *
from functools import *
from itertools import *
from collections import *
from typing import *
from bisect import *
import random
sys.setrecursionlimit(10 ** 5)

def rarray():
	return [int(i) for i in input().split()]
t = 1
for ii in range(t):
	(n, p) = rarray()
	a = rarray()
	a.sort()
	(al, ar) = (a[0], a[p - 1] - 1)
	for i in range(n):
		(l, r) = (al + i, ar + i)
		if i + p - 1 < n:
			r = min(r, a[i + p - 1] - 1)
		if i + 1 < n:
			l = max(l, a[i + 1] - 1)
		al = max(al, l - i)
		ar = min(ar, r - i)
	if al > ar:
		print(0)
		print()
		continue
	print(ar - al + 1)
	for i in range(al, ar + 1):
		print(i, end=' ')
	print()


import sys, math, os
from io import BytesIO, IOBase
from collections import defaultdict as dd, deque, Counter

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

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
INF = 10 ** 9
mod = 998244353
(n, p) = mdata()
A = mdata()
A.sort()
m = 0
m1 = -INF
l = []
for i in range(n):
	m = max(m, A[i] - i)
for i in range(p - 1, n):
	m1 = max(m1, i - A[i] + 1)
i = m
while True:
	if m1 + i >= p:
		break
	l.append(i)
	i += 1
out(len(l))
outl(l)


import bisect

def f(x):
	for i in range(n):
		z = bisect.bisect_right(li, x + i)
		if (z - i) % p == 0:
			return 0
	return 1

def find_right(left, right):
	mid = (left + right) // 2
	if f(mid):
		if f(mid + 1) == 0 or right == mid:
			return mid
		return find_right(mid + 1, right)
	if left == mid:
		return '0'
	return find_right(left, mid - 1)
l = input().split()
n = int(l[0])
p = int(l[1])
l = input().split()
li = [int(i) for i in l]
l = []
li.sort()
maxa = 0
for i in range(n):
	maxa = max(li[i] - i, maxa)
z = find_right(maxa, li[-1])
if z == '0':
	print(0)
	print()
	exit()
print(z - maxa + 1)
for i in range(maxa, z + 1):
	print(i, end=' ')


import sys
input = lambda : sys.stdin.readline().rstrip()
(n, p) = map(int, input().split())
A = sorted([int(i) for i in input().split()])
A = [A[i] - int(i) for i in range(n)]
AA = [A[-1]]
for i in range(n - 1):
	AA.append(min(AA[-1], A[n - 2 - i]))
AA = AA[::-1]
Ans = []
for i in range(max(A), max(A) + p + 1):
	if i - AA[p - 1] + 1 < p:
		Ans.append(i)
print(len(Ans))
print(*Ans)


(n, p) = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
m = l[-1]
b = [0] * (2 * n - 1)
ind = 0
for i in range(2 * n - 1):
	while ind < n and l[ind] <= i + m - n + 1:
		ind += 1
	b[i] = ind
chuje = [0] * p
for i in range(m - n + 1, m + 1):
	chuje[(i - b[i - m + n - 1]) % p] += 1
dobre = []
for x in range(m - n + 1, m):
	if not chuje[x % p]:
		dobre.append(x)
	chuje[(x - b[x - m + n - 1]) % p] -= 1
	chuje[(x + n - b[x - m + 2 * n - 1]) % p] += 1
print(len(dobre))
print(*dobre)