Editorial

Firstly, let's sort an array.

Consider a greedy solution for some $k$. For the first integer in the set, we will choose the minimal element. Then let $x$ be the last chosen element. The next element will be the smallest integer from the array which is at least $x+k$. And we will do this till there is such an integer.

Here is a proof of why it works. Let $x_1,\dots ,x_k$ be a sequence that we get from the greedy solution and let $y_1,\dots ,y_{k+1}$ be some better sequence (if we can get even better, then take a subsequence of it of $k+1$ elements). Then, we will prove that the greedy solution should get sequence $y$. Clearly, there exists some $j$, such that $x_j<y_j$, because otherwise these sequences should be equal (there cannot exist index $l$ such that $x_l>y_l$, since we always choose the smallest possible $x_l$). We will choose the smallest such $j$. Then, $x_j$ is the smallest element which is good for us, so if we make $y_j$ equal to $x_j$ in sequence $y$, it should also be good and it doesn't change the number of elements. If we do this till we can, at some moment we will see that the first $k$ elements are equal in $x$ and $y$, but $y$ has also one more, so we get a contradiction.

So, how long does this algorithm work? We can make it in $O(n)$ by iterating over all elements and updating the last elements. Using binary search, we can make it in $O(\frac{A}{k}\cdot \log (n))$, if we search for the next element in the sequence. This is already good enough (if you implement it using actual binary search and not $\text{std::set}$), but we can solve it in $O(\frac{A}{k})$. It would be good for us, because in this case, the final complexity will be $\frac{A}{1}+\cdots +\frac{A}{n}=A\cdot (\frac{1}{1}+\cdots +\frac{1}{n})\le A\cdot \log (n)$ which is good. (Using binary search you will get $O(A\cdot {\log }^2(n))$). To get $O(\frac{A}{k})$ for fixed $k$, for each element $x$, we can memorize the next element in the array which is at least $x$. If we add $5\cdot 10^5$ to all elements (note that it will not change the answer), we can make an array of $10^6$ integers where the $i$-th integer is the smallest number in the array which is at least $i$. It can be computed in $O(A)$. Then, we can find the next element in thegreedy solution in $O(1)$ just by looking at the $x+k$-th element of the array.