Define a permutation $(a_1,\dotsc,a_n)$ of $(1,\dotsc,n)$ as $n$-cool if it satisfies the problem's statement. Also, let the number of $n$-cool permutations be $S_n$ Taking $k=n-1$, one must have $1+2+\dotsc + (n-1)=a_1+\dotsc+a_{n-1}$ or $1+2+\dotsc + (n-1)=a_2+\dotsc+a_{n}$. This implies $n=a_n$ or $n=a_1$. Furthermore, this implies that one of $(a_1,\dotsc,a_{n-1})$ or $(a_2,\dotsc,a_n)$ is $(n-1)$-cool. Next, we see that any $(n-1)$-cool permutation can be made $n$-cool by adding $n$ to the front or end of the tuples. Therefore, we have \[ S_n=2S_{n-1}. \]Considering that $S_1=1$, we have $\boxed{S_n=2^{n-1}}$ by induction.