[proofplan] We classify indices according to whether the corresponding term dominates every later term. If infinitely many such peak indices exist, listing them in increasing order immediately gives a nonincreasing subsequence. If only finitely many exist, then after the last peak every index has a later index with strictly larger value, and a recursive construction gives a strictly increasing subsequence. These two exhaustive cases produce a monotone subsequence in all possibilities. [/proofplan] [step:Define peak indices and split into the two exhaustive cases] Let $P \subset \mathbb{N}$ denote the set of peak indices, defined by \begin{align*} P := \{n \in \mathbb{N} : a_n \geq a_m \text{ for every } m \in \mathbb{N} \text{ with } m > n\}. \end{align*} Thus an index $n$ belongs to $P$ exactly when the term $a_n$ is at least as large as every term that occurs strictly later in the sequence. The set $P$ is either infinite or finite. We treat these two cases separately. [/step] [step:List infinitely many peak indices to obtain a nonincreasing subsequence] Assume first that $P$ is infinite. Since $P$ is an infinite subset of $\mathbb{N}$, there exists a strictly increasing sequence of indices \begin{align*} p: \mathbb{N} &\to P \end{align*} whose image is contained in $P$. Write $p_k := p(k)$ for each $k \in \mathbb{N}$, so that \begin{align*} p_1 < p_2 < p_3 < \cdots . \end{align*} For each $k \in \mathbb{N}$, the inequality $p_{k+1} > p_k$ and the defining property of the peak index $p_k$ imply \begin{align*} a_{p_k} \geq a_{p_{k+1}}. \end{align*} Therefore the subsequence $(a_{p_k})_{k=1}^{\infty}$ is nonincreasing, hence monotone. [guided] Assume that there are infinitely many indices whose terms dominate everything to their right. We collect these indices in increasing order. Formally, since $P$ is an infinite subset of $\mathbb{N}$, we may choose a map \begin{align*} p: \mathbb{N} &\to P \end{align*} such that, writing $p_k := p(k)$, the indices satisfy \begin{align*} p_1 < p_2 < p_3 < \cdots . \end{align*} Now fix $k \in \mathbb{N}$. Because $p_k$ is a peak index, its defining property says that $a_{p_k} \geq a_m$ for every later index $m > p_k$. Since $p_{k+1} > p_k$, we may take $m = p_{k+1}$ and obtain \begin{align*} a_{p_k} \geq a_{p_{k+1}}. \end{align*} This inequality holds for every $k \in \mathbb{N}$. Hence the selected terms decrease in the non-strict sense: \begin{align*} a_{p_1} \geq a_{p_2} \geq a_{p_3} \geq \cdots . \end{align*} Thus $(a_{p_k})_{k=1}^{\infty}$ is a nonincreasing subsequence, which is monotone under the non-strict convention. [/guided] [/step] [step:Recursively choose later indices with strictly larger values when peaks are finite] Assume now that $P$ is finite. Choose $N \in \mathbb{N}$ such that every peak index belongs to $\{1,\dots,N\}$. Define a sequence of indices $(q_k)_{k=1}^{\infty}$ recursively as follows. Set \begin{align*} q_1 := N+1. \end{align*} Suppose $q_k$ has been chosen. Since $q_k > N$, the index $q_k$ is not a peak. Therefore there exists an index $q_{k+1} \in \mathbb{N}$ such that \begin{align*} q_{k+1} > q_k \end{align*} and \begin{align*} a_{q_{k+1}} > a_{q_k}. \end{align*} This recursively defines a strictly increasing sequence of indices $(q_k)_{k=1}^{\infty}$, and the corresponding subsequence satisfies \begin{align*} a_{q_1} < a_{q_2} < a_{q_3} < \cdots . \end{align*} Thus $(a_{q_k})_{k=1}^{\infty}$ is strictly increasing, in particular nondecreasing, hence monotone. [guided] Now assume that only finitely many peak indices exist. Because $P$ is finite, we can choose an integer $N \in \mathbb{N}$ such that all peak indices are among $1,\dots,N$. Equivalently, no index larger than $N$ is a peak. We start after all possible peaks by defining \begin{align*} q_1 := N+1. \end{align*} This ensures that $q_1$ is not a peak. More generally, once an index $q_k > N$ has been chosen, it is also not a peak. Unpacking the negation of the definition of peak gives the key point: since $q_k \notin P$, it is not true that $a_{q_k} \geq a_m$ for every $m > q_k$. Therefore there must be some later index $q_{k+1} \in \mathbb{N}$ such that \begin{align*} q_{k+1} > q_k \end{align*} and \begin{align*} a_{q_{k+1}} > a_{q_k}. \end{align*} This recursive rule constructs indices that move strictly to the right, so \begin{align*} q_1 < q_2 < q_3 < \cdots . \end{align*} It also constructs terms that strictly increase: \begin{align*} a_{q_1} < a_{q_2} < a_{q_3} < \cdots . \end{align*} Thus $(a_{q_k})_{k=1}^{\infty}$ is a strictly increasing subsequence. Since every strictly increasing sequence is nondecreasing, this subsequence is monotone. [/guided] [/step] [step:Conclude that a monotone subsequence always exists] The two cases are exhaustive. If $P$ is infinite, the subsequence constructed from the peak indices is nonincreasing. If $P$ is finite, the recursively constructed subsequence is strictly increasing and therefore nondecreasing. In either case, the original real sequence $(a_n)_{n=1}^{\infty}$ has a monotone subsequence. [/step]