## Combinatorics proof help

Prove that in any sequence $a_1, a_2,...,a_{mn+1}$ of $mn+1$ distinct real numbers, there are either $m+1$ numbers (not necessarily consecutive) that occur in increasing order, or $n+1$ that occur in decreasing order.

HINT: For each term $a_i$, consider the ordered pair $(x_i, y_i)$, where $x_i$ and $y_i$ are the lengths of the longest increasing and decreasing subsequences ending with $a_i$. The conclusion holds if there is an $i$ for which $x_i \geq m+1$ or $y_i\geq n+1$.

I've seen a proof for this which involves $x_i$ and $y_i$ where one is a subsequence ending in $a_i$ and the other begins with $a_i$ but this hint is different. Can someone help me get started?