Editorial

Since $K\leq N$ , the sequence $X$ contains every integer from $2$ through $K+1$ . Therefore, the $K$ -th smallest number in $X$ is always $K+1$ .

The required output is $(K+1)\bmod 998\ 244\ 353$ . Compute and output this value without constructing $P$ , $C$ , or .

Both the time complexity and the auxiliary space complexity are $O(1)$ .

Proof

Choose any integer $m$ with $2\leq m\leq K+1$ . The number $m$ is either prime or composite.

There are $m-1$ integers from through . Thus, if is prime, its rank among the primes is at most . If it is composite, its rank among the composites is at most .

Solution written by GPT6

Sorting a Sequence

Editorial