Comment by dmehrle

Subsequences need not be contiguous. In your example, taking every other number gives the desired monotone subsequence.