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?