This question is motivated by this post, [Can you identify the sum of two permutations in polynomial time?][1] , 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 differences sequence of permutation $2 3 4 1$.  While, sequences $2, 2, 3$ and $ 3, 1, 2$ are not the differences sequence of any permutation of numbers $1, 2, 3, 4$. 

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

**EDIT**: We get computationally equivalent problem if we formulate the problem using circular permutations.

**EDIT2**: Cross posted on MathOverflow, [How hard is reconstructing a permutation from its differences sequence?][2]

**EDIT3** Awarded the bounty to the proof sketch and I would accept the answer after getting the complete formal proof.

**EDIT 4**: Marzio's nice $NP$-completeness proof has been published in [the Electronic Journal of Combinatorics][3].

[1]: https://cstheory.stackexchange.com/questions/18037/can-you-identify-the-sum-of-two-permutations-in-polynomial-time/18045#18045
[2]: http://mathoverflow.net/questions/135968/how-hard-is-reconstructing-a-permutation-from-its-differences-sequence
[3]: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p3