Calculate in recursion the number of permutations of the numbers $1,\dots, N$ in which each number is greater than all those to its left or smaller than all those to its left.
I tried to look at the base cases, and I got this recursion: $p(n)= n\cdot p(n-1)$ but I think it doesn't work in all cases.
Given that there is one such permutation for $N=1$, your recursion would give $N!$ permutations satisfying the condition, that is all permutations, so is clearly not correct.
Hint: work right to left. What are the possible values of the rightmost element of the permutation? Note that once this element is removed, you are left with a permutation of the remaining $N-1$ elements satisfying the same condition.