khba Loves to Sleep!

We need maximize the time until the first friend reaches a teleport.

For chosen teleport positions $S$, friend $i$ reaches the nearest teleport after

$$\min_{s\in S}|a_i-s|.$$

The first friend arrives after

$$\min_i \min_{s\in S}|a_i-s|.$$

That is just the minimum distance between any chosen teleport and any friend. So each teleport position has its own score:

$$d(p)=\min_i |p-a_i|.$$

We need choose the $k$ distinct integer positions in $[0,x]$ with the largest scores $d(p)$. There is no extra spacing condition between teleports. If two great spots are adjacent, take them both. The teleports are not allergic to each other.

Compress the friends

Duplicate friend positions do not change distances, so sort $a$ and erase duplicates.

Now look at the free integer positions by regions:

• Left edge: $[0, a_0-1]$
• Right edge: $[a_{m-1}+1, x]$
• Middle gaps: $(a_i, a_{i+1})$
• Friend positions themselves, which have distance $0$

If the optimal distance is positive, friend positions are useless. But if everything else is exhausted, distance $0$ positions may be needed, so the implementation handles them too.

Counting positions with distance at least $D$

Define $count(D)$ = number of integer positions $p\in[0,x]$ such that $d(p)\ge D$.

For $D=0$, every position works, so $count(0)=x+1$.

For $D>0$:

Left edge positions must be at most $a_0-D$, so there are

$$\max(0, a_0-D+1)$$

positions.

Right edge positions must be at least $a_{m-1}+D$, so there are

$$\max(0, x-(a_{m-1}+D)+1)$$

positions.

For a gap between consecutive friend positions $L$ and $R$, a valid teleport must satisfy both:

$$p-L\ge D$$

and

$$R-p\ge D.$$

So

$$L+D\le p\le R-D.$$

That contributes

$$\max(0, R-L-2D+1)$$

positions.

This gives an $O(n)$ checker. Binary search the largest $D$ with $count(D)\ge k$.

Call this distance $best$.

Building the actual answer

After binary search, every position with distance greater than $best$ is definitely in the top group. Positions with distance exactly $best$ are tied for the cutoff. So:

1. Output positions with $d(p)>best$.
2. Then output arbitrary positions with $d(p)=best$ until there are $k$ total.

Instead of calculating $d(p)$ one by one over the gigantic range, generate these positions region-by-region.

For a threshold $D$, all positions with $d(p)\ge D$ are exactly:

• left edge: $0$ through $a_0-D$
• right edge: $a_{m-1}+D$ through $x$
• gap $(L,R)$: $L+D$ through $R-D$

So we can have a helper add(D, strict):

• if strict = true, add positions with distance at least $best+1$, i.e. distance $>best$;
• if strict = false, add positions with distance at least $best$, skipping already-added positions.

A set is used only while constructing the output to avoid duplicates between passes. Since we stop after $k$ positions and total $k$ over all tests is bounded, this is totally fine.

When $best=0$, the second pass with threshold $0$ can simply fill remaining positions from friend positions or, more generally, from $0,1,2,\dots,x$ while skipping already used positions. Since $k\le 2\cdot 10^5$, this loop stops quickly. No billion-step nonsense.

Correctness proof

Let $d(p)$ be the distance from position $p$ to the nearest friend.

First, for any chosen teleport set $S$, the objective value is

$$\min_i \min_{s\in S}|a_i-s|.$$

This equals

$$\min_{s\in S} d(s),$$

because $d(s)$ is already the nearest-friend distance for teleport position $s$. Therefore the quality of a teleport set is the minimum score among its chosen positions.

So an optimal solution is obtained by choosing the $k$ positions with largest $d(p)$ values. If the $k$-th largest distance is $T$, then every chosen position must have distance at least $T$, and there must be at least $k$ positions with distance at least $T$.

The counting formula for $count(D)$ is exact because sorted friend positions partition the line into edge regions and gaps. On each edge, only one nearest friend can constrain the distance. In each middle gap $(L,R)$, the nearest friend is one of the two endpoints, so a point is distance at least $D$ from all friends exactly when it is at least $D$ away from both $L$ and $R$, giving $L+D\le p\le R-D$.

Thus $count(D)$ is exactly the number of positions whose score is at least $D$. Since $count(D)$ is non-increasing as $D$ grows, binary search finds the maximum feasible distance $best$ with $count(best)\ge k$.

All positions with distance greater than $best$ must be selected before any position with smaller distance. Since $best$ is maximal feasible, fewer than $k$ positions have distance greater than $best$. The construction first outputs all available positions with distance greater than $best$, then fills with positions of distance at least $best`. Therefore every output position has score at least the$k$-th largest score, and exactly$k$ distinct positions are output.

So the minimum friend-teleport distance of the constructed set is optimal.

Complexity

For each test case, sorting costs $O(n\log n)$.

The binary search runs $O(\log x)$ checks, each $O(n)$.

Construction outputs at most $k$ positions plus scans the gaps, so it is $O(n+k)$.

Overall:

$$O(n\log n+n\log x+k)$$

per test case, easily inside the limits.