$3\mathrm{.}1$ Non$-$Adaptive Sort $(7$ pt$.)$ We say that a comparison$-$based sorting algorithm is non$-$adaptive if it commits in advance to the pairs of elements that it will compare. For example, consider a sorting algorithm which commits in advance to compare all possible pairs of elements. And then it uses the comparisons to find the kth smallest element for each k$,$ thereby sorting the input array. Prove that any non$-$adaptive sorting algorithm requires $($n $2)$ comparisons.

$[$We are expecting: A succinct but rigorous proof. It$$s OK to prove the lower bound for deterministic algorithms, although you may want to challenge yourself and prove it for randomized algorithms $($with expected number of queries$).]$