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$.

Difficulty: interview

Starter code:

Solutions:
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=" ")

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


# T = int(input())
# for _ in range(T):
n, p = list(map(int, input().split()))
matrix = list(map(int, input().split()))
res = solve(n, p, matrix)
print(len(res))
print(" ".join(map(str, res)))


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

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

mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import Counter
    input = sys.stdin.readline
    N, p = list(map(int, input().split()))
    A = list(map(int, input().split()))
    A.sort()

    """
    C = Counter(A)
    for a in A:
        if C[a] >= p:
            print(0)
            print("\n")
            return
    """
    x0 = -1
    for i in range(N):
        x0 = max(x0, A[i] - i)
    x1 = A[p-1]
    """
    if x0 >= x1:
        print(0)
        print("\n")
        return
    """

    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)


def __starting_point():
    main()

__starting_point()

n, p = list(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 sys
lines = sys.stdin.readlines()
# (N, K) = map(int, lines[0].strip().split(" "))
(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()

#!usr/bin/env python3
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
def __starting_point():
    solve()

__starting_point()

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))
		# print (num,count)
		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))
		# print (num,count)
		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)

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=' ')
""" print('max ', _max)
print('min ', _min) """


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)

def __starting_point():
	main()
__starting_point()

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



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)

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()
#print(query)
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)


n, p = map(int, input().split())
a = list(map(int, input().split()))


a = sorted(a)
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(*[val for val in range(l, r)])

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

# f = open('test.py')
# def input():
# 	return f.readline().replace('\n','')

# import heapq
# import bisect
# from collections import deque
# from collections import defaultdict
def read_list():
	return list(map(int,input().strip().split(' ')))
def print_list(l):
	print(' '.join(map(str,l)))

# N = int(input())
# for _ in range(N):
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)
# print(dic)

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)