How close is the median of a uniformly chosen subsample to the median of the full set?

Question

Take $N$ a set of n numbers, sample s numbers from $N$ uniformly and with replacement giving us the set $S$.

What is the relationship between the median of $N$ and the median of $S$ ?

I want a result that looks like:

With probability ... the median of $S$ has a rank in $N$ in $\left[\left(\frac12 - d\right)n, \left(\frac12 + d\right) n\right]$.

I am actually interested in a proof of Lemma 13 of https://dl.acm.org/doi/pdf/10.1145/3409964.3461790 (which comes without a proof)

Thanks :)