Erdos-Szekeres Theorem

Prove that for given integers $r, s$ any sequence of distinct real numbers of length at least $(r - 1)(s - 1) + 1$ contains either a monotonically increasing subsequence of length $r$, or a monotonically decreasing subsequence of length $s$.

Prove that every sequence of $n^2$ distinct numbers contains a subsequence of length $n$ which is monotone (i.e. either always increasing or always decreasing).