Prove that every unbounded sequence contains a monotone subsequence that diverges to inifnity.

I think I have the basic framework for this proof, but I am having trouble putting everything together in a convincing way.

I plan on showing that by the definition, an unbounded sequence $(a_n)$ has infinitely many $n$ such that $a_n>M$ where $M>0$, for some natural number $n$. I'm not sure how it is implied that there exists some $a_{n_k}$ such that $a_{n_k}>M$ for some natural number $k$. Let me know if I'm on the right track, and please help me string these ideas together!

Assuming that the sequence is unbounded above, then you can generate your monotone divergent sequence as follows.

Choose $n_1$ to be the first index such that $a_{n_1} > 1$. Now, from the remaining sequence, choose $n_2 > n_1$ to be the first index such that $a_{n_2} > 2$ and $a_{n_2} > a_{n_1}$.

Rinse. Repeat.

For each $k \in \mathbb{N}$, you have $a_{n_k} > k$ and $a_{n_k} > a_{n_{k-1}}$, so the subsequence $\left( a_{n_k} \right)$ certainly diverges to infinity.

Why do you know that you can always find such an index? If you could not, then your sequence must have been bounded.

You surely should use that there are infinitely many $n$'s such that $|a_n| > M$ for any real $M$. Consider one of positive and non-positive subsequences. At least one of them is not bountded, too. So you have right to assume without lose of generality that there are infinitely many $n$'s such that $a_n > M$ for any real $M$. If follows that there are infinitely many such $n$'s greater any $n'$. And so you may choose any $a_i$ and let $M = a_i$ to find $j$ such that $j>i$ and $a_j > a_i$. Do you see how to get monotonic subsequence converging to $+\infty$?