KöMaL 2019 A759

We choose a random permutation of numbers $1, 2,\dots, n$ with uniform distribution. Prove that the expected value of the length of the longest increasing subsequence in the permutation is at least $\sqrt{n}\,$.