human
Solve in Python:
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...
assistant
#Here is Python code to find all good integers $x$.

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