Prove that in any sequence of distinct real numbers, there are either numbers (not necessarily consecutive) that occur in increasing order, or that occur in decreasing order.
HINT: For each term , consider the ordered pair , where and are the lengths of the longest increasing and decreasing subsequences ending with . The conclusion holds if there is an for which or .
I've seen a proof for this which involves and where one is a subsequence ending in and the other begins with but this hint is different. Can someone help me get started?