Solution
= Solution
Replacing one input coordinate changes the <longest increasing subsequence> length by at most one, so $Z=L(X)$ has the <bounded differences property> with $c_i=1$. The two-sided <McDiarmid inequality> gives, for $t\geq0$,
$$
\mathbb P(Z-\mathbb EZ>t)
\leq e^{-2t^2/n},
\qquad
\mathbb P(Z-\mathbb EZ<-t)
\leq e^{-2t^2/n}.
$$