Let $P(n)$ the number of the permutation then $P(n+1)=P(n)+1$ so $P(n)=n$.

@above I found $P(3)=4$ by hand. I hope this solution is true. Let $P(n)$ denote the number of such permutations. If $(x_1,x_2,...,x_n)$ is such a permutation we have $x_n \in \{1,n\}$ otherwise both $1$ and $n$ would be in first $n-1$ number. $i)$ Number of such permutations with $x_n=n$ is $P(n-1)$. $ii)$ Let $x_n=1$. We have $\{x_{n-1},x_n\} \in \{\{1,2\},\{1,n\},\{2,n-1\},\{n-1,n\}\}$ by looking at first $n-2$ numbers. If $x_{n-1}=n$ then we can arrange $2,3,...,n-1$ in $P(n-2)$ different ways. It also satisfies the condition for first $n-1$ and $n$ numbers. If $x_{n-1}=2$ then we can arrange $3,4,...,n-1$ in $P(n-2)$ different ways. Thus $P(n)=P(n-1)+2P(n-2) \implies P(n)=2^{n-1}$