Increasing or decreasing subsequence

Pairs. For each element $a_k$, let $\text{inc}_k$ be the length of the longest increasing subsequence ending at $k$, and $\text{dec}_k$ similarly for decreasing.

Distinctness. If $i<j$ and $a_i<a_j$, then $\text{inc}_j>\text{inc}_i$. If $a_i>a_j$, then $\text{dec}_j>\text{dec}_i$. So all pairs $(\text{inc}_k,\text{dec}_k)$ are distinct.

Pigeonhole. Each coordinate is at most $n$ if no inc or dec subsequence of length $n+1$ exists. So at most $n^2$ distinct pairs. But there are $n^2+1$ elements. Contradiction.

Conclusion. Either an increasing or a decreasing subsequence of length $n+1$ exists. (Erdős–Szekeres theorem.)