This question is motivated by this post, Can you identify the sum of two permutations in polynomial time? , and my interest in computational properties of permutations.

A differences sequence $a_1, a_2, \ldots a_n$ of a permutation $\pi$ of numbers $1, 2, \ldots n+1$ is formed by finding the difference between every two adjacent numbers in the permutation $\pi$. In other words, $a_i= |\pi(i+1)-\pi(i)|$ for $1 \le i \le n$

For example, sequence $1, 1, 3$ is the difference sequence of permutation $2 3 4 1$. While, sequences $2, 2, 3$ and $ 3, 1, 2$ are not the difference sequence of any permutation of numbers $1, 2, \ldots ,4$.

Is there an efficient algorithm to determine whether a given sequence is the difference sequence for some permutation $\pi$, or is it NP-hard?