All permutations of $1,2,...,n$ such that each element is larger than all previous elements or smaller than all previous elements
Think about choosing the permutation in reverse order $a_n,a_{n-1},\dots,a_1$. Each element must be highest or smallest of the elements not previously chosen, so there are two choices for each (except for $a_1$, where the highest and lowest are the same).
For example, the last element is always $1$ or $n$. If the last element is $1$, then the second to last is either $2$ or $n$. And so on $\dots$.
What I think the hint is trying to say:
Suppose that our current string is $a_1a_2a_3\cdots a_k$. Then either $a_{k+1}$ must be $\max\{a_1, \ldots, a_k\}+1$ or $\min\{a_1, \ldots, a_k\}-1$. If any other choice is made, then either $\max\{a_1, \ldots, a_k\}+1$ or $\min\{a_1, \ldots, a_k\}-1$ will not be legally allowed to be placed. Of course one needs to be careful with when either of these values doesn't exist (i.e. when either $1$ or $n$ has already been used). It's not clear to me how to fill in this gap.
Here's probably the simplest inductive argument.
Base cases up to $n=2$ are easy.
Suppose that the proposition is true for the case $n-1$.
First, notice that we have only two choice for $a_n$, as it must always be either $1$ or $n$. If not, then both $1$ and $n$ appear before $a_n$ (because $n \geq 3$) which means it can't be good.
If $a_n = 1$, then $a_1-1, \cdots a_{n-1}-1$ is a good sequence of length $n-1$, so there are $2^{n-2}$ choices for the other elements.
If $a_n = n$, then $a_1, \cdots a_{n-1}$ is a good sequence of length $n-1$, so there are $2^{n-2}$ choices.
In total then, there are $2^{n-2} + 2^{n-2} = 2^{n-1}$ choices.
Note that the first two elements in the sequence must be adjacent to each other, but their order is irrelevant. So given a GOOD sequence $a_1,\ldots,a_n$ of length $n$, we can generate two GOOD sequences of length $n+1$:
$$a_1,a_1+1,b_2,\ldots,b_n$$ and $$a_1+1,a_1,b_2,\ldots,b_n$$
where $b_i=a_i$ if $a_i<a_1$, and $b_i=a_i+1$ if $a_i>a_1$. For instance, the sequence $23145$ generates $234156$ and $324156$. So we see that there are twice as many GOOD sequences of length $n+1$.