The $N(n)$ is exponential in $n$. First, I present a lower bound. The construction is recursive. Call a sequence whose first differences are monotone, *$1$-monotone*. Suppose $\mathbf{a}=a_1,\dotsc,a_M$ is a sequence that contains no $1$-monotone $N$-term subsequence. Pick an number $R$ that is larger than $\max_{i,j}(a_i-a_j)$. Then the sequence $\mathbf{b}=a_1,\dotsc,a_M,a_1+R,\dotsc,a_M+R$ contains no $1$-monotone subsequence of length $N+1$. Indeed, the subsequence cannot contain $N$ elements from the same half of $\mathbf{b}$. Hence, it must contain at least $2$ elements from each of the halves, which is impossible by the choice of $R$.

The upper bound is also recursive. We will find a monotone increasing subsequence with a stronger property that either $a_i-a_1\leq a_{i+1}-a_i$ or $a_{last}-a_i\leq a_i-a_{i-1}$. Suppose we are given a sequence $\mathbf{a}$. We may assume that it is monotone increasing (by losing only a square, and reversing the sequence if necessary).  Let $X$ be the median of $\mathbf{a}$. The median splits $\mathbf{a}$ into two equally long sequences $\mathbf{b}$ and $\mathbf{c}$. By induction we can find $1$-monotone subsequences $\mathbf{b}'$ and $\mathbf{c}'$ in $\mathbf{b}$ and $\mathbf{c}$ respectively. If $X-a_1\leq a_{last}-X$, then
the concatenation of $\mathbf{b}'$ with $a_{last}$
is the desired sequence. If $X-a_1\geq a_{last}-X$
then the concatenation of $a_1$ with $\mathbf{c}'$ is a desired subsequence.