Let $f(n)$ is number of such permutations and $f_i(n)$ is number of such permutations where $a_i=n$ Then $f(n)=f_1(n)+...+f_n(n)$ $f(2)=1$ $f_n(n)=f(n-1)$ If $a_i=n$ than $a_1<a_2<...<a_{i-1}$ and $a_{i+1}<a_{i+2}<...<a_n$ so $ f_i(n)= C_{n-1}^{i-1}$ $f_1(n)+f_2(n)+...+f_{n-1}(n)= C_{n-1}^0+C_{n-1}^1+...+C_{n-1}^{n-2}=2^{n-1}-1$ $f(n)=f(n-1)+2^{n-1}-1$ $f(n)=f(n-1)+2^{n-1}-1=f(n-2)+2^{n-1}-1+2^{n-2}-1=...=f(2)+ 2^{n-1}+...2^2-(n-2)=2^n-n-1$