If the sequence is unbounded the problem is trivial so assume it is bounded. Now by the Bolzano-Weierstrass thereom there exists an increasing sequence of $k_1,k_2,...$ such that $a_{k_1}, a_{k_2},...$ converges. Either infinitely many of the terms are $\ge$ the limit or $\le$ it. WLOG $\ge$. Then its trivial to find a nonincreasing subsequence that is $\ge$ the limit using the definition of a limit so we are done.

dinoboy used Bolzano-Weierstrass to prove this, in fact some texts use this result to prove Bolzano Weierstrass. Here is a purely combinatorial proof: Suppose no infinite non-decreasing sequence exists. Then in particular there exists a maximum $a_{m_1}$. Now consider the sequence $(a_i)_{i>m_1}$, again it has no infinite non-decreasing sequence and thus has a maximum $a_{m_2}$, continue in this was to construct a sequence $a_{m_1}, a_{m_2}, \ldots $. Clearly $a_{m_{i}} \geq a_{m_{i+1}}$ since at each time we are choosing a maximum.

Neat result but not suitable for oly's. A problem shouldn't be trivialized by obscure theorems Call an $a_k$ maximal if $a_k \geq a_i$ for all $i \leq k$ and define minimality similarly. We get two cases. Case 1: the number of minimal or maximal terms is infinite. the infinite maximal or minimal terms must be increasing or non increasing. Case 2: the number of minimal and maximal terms is finite. If this is the case, sequence is bounded. By a kind of obscure theorem that I don't know the name, we can define an increasing sequence $k_1,k_2,...$ where $a_{k_1}+a_{k_2}+ \cdots$ converges. We have either $a_{k_{i+1}} \geq a_{k_i}$ or $a_{k_{i+1}} \leq a_{k_i}$ occuring infinitely many times, giving the desired sequence.