Asterism (Hard Version)
Contest: Codeforces Round 654 (Div. 2)
Difficulty rating: 2300
Tags: binary search, combinatorics, dp, math, number theory, sortings

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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

Example input:
3 2
3 4 5

Example output:
1
3

Example input:
4 3
2 3 5 6

Example output:
2
3 4

Editorial:
There are two different solutions to solve this problem.
Solution 1:
First, find the minimum $$$s$$$ which has $$$f(s) > 0$$$. You can use binary search or cumulative sum for it.
Now, we can say the answers form a segment $$$[s,t]$$$ (or there are no answers). Find $$$t$$$ and proof this.
Let's define $$$b_i$$$ as the number of the enemies who has equal or less than $$$i$$$ candies.
Then, observe the value $$$C_i(x) = b_{x+i}-i \ (0 \le i \le N-1)$$$ :
• $$$f(x) = \prod_{i=0}^{N-1} C_i(x)$$$
• once the value $$$C_i(x)$$$ exceed $$$p$$$ , $$$f(x)$$$ is divisible by $$$p$$$ because $$$C(x)$$$ is decremented by (at most) 1 in one step and contains some $$$C_i(x) = p$$$ in this $$$x$$$.
• $$$C_i(x) \le C_i(x+1)$$$ are always satisfied.
• Then, once $$$f(x)$$$ is divisible by $$$p$$$ , $$$f(x+\alpha)$$$ is also divisible by $$$p$$$, so $$$t$$$ can be find by using binary search.
• We can find $$$t$$$ without binary search by the following method:1. let $$$i \leftarrow 0, t \leftarrow max(A)$$$ 2. if($$$C_i(t)<p$$$){i++;}else{t–;}3. Repeat the step 2. And when become $$$i=N$$$ and the algorithm stops, $$$t$$$ is the maximum value which we want.
Solution 2:
We can say that $$$f(x) = \prod\limits_{i=x}^{x+n-1} b_i-(i-x) = \prod\limits_{i=x}^{x+n-1} x-(i-b_i)$$$ .
We should find all $$$x \in \mathbb{Z}$$$, such that there is no $$$x \leq i < x + n$$$, such that $$$x \equiv i - b_i \, (\bmod p)$$$.
It's easy to see, that there should be $$$max(a_i) - n \leq x \leq max(a_i)$$$ to have $$$f(x) \neq 0$$$ and $$$f(x) \neq n!$$$ (they are both divisible by $$$p$$$).
Let's calculate $$$i - b_i$$$ for all necessary values $$$max(a_i) - n \leq x \leq max(a_i) + n$$$ and after that we can solve the problem by $$$O(n)$$$.
Anyway, the total complexity is $$$O(n)$$$ or $$$O(n \log n)$$$.