Give an O(n lg n)-time algorithm to find the longest monotonically increasing subsequence of a sequence of n numbers. Observe that the last element of a candidate subsequence of length i is at least as large as the last element of a candidate subsequence of length i - 1. Maintain candidate subsequences by linking them through the input sequence.