$NP$-completeness of recognizing the difference of two permutations Shor stated, in his comment to anonymous moose's answer to this question Can you identify the sum of two permutations in polynomial time?, that it is $NP$-complete to identify the difference of two permutations. Unfortunately, I don't see a straightforward reduction from the permutation sum problem and it is useful to have the $NP$-completeness reduction for the permutation difference problem. 

Permutation Difference:

INSTANCE: An array $A[1...n]$ of positive integers. 

QUESTION: Do there exist two permutations $\pi$ and $\sigma$ of the positive integers $1,2, ... , n$ such that $|\pi(i) - \sigma(i)| = A[i]$ for $1 \le i \le n$ ? 


  What is the reduction for proving the $NP$-completeness of recognizing the difference of two permutations?


EDIT 10-9-2014: Shor's comment gives a reduction which proves $NP$-completeness when the elements of sequence $A$ are signed differences. However, I don't see an easy reduction to my problem where all elements of $A$ are the absolute values of differences.

UPDATE: The Permutation Difference problem seems to be $NP$-complete even if one of the two permutations is always the identity permutation. Hardness proof of this special case is very welcome. So, I am interested in $NP$-completeness of this restricted version:

Restricted Permutation Difference:
INSTANCE: An array $A[1...n]$ of positive integers. 

QUESTION: Does there exist a permutation $\pi$ of the positive integers $1,2, ... , n$ such that $|\pi(i) - i| = A[i]$ for $1 \le i \le n$ ? 

Update 2: The restricted problem is efficiently decidable as shown by mjqxxxx's answer. The computational complexity of the original problem is not proven. 

EDIT 9/6/16: I am interested in determining whether this simplification of Permutation Difference is NP-complete:

Restricted Permutation Difference:

INSTANCE: A multiset $A$ of positive integers. 

QUESTION: Does there exist a permutation $\pi$ of the positive integers $1,2, ... , n$ such that  $A= \{|\pi(i) - i| :1 \le i \le n\}$ ?
The restricted problem, where one of the permutations is the identity, is certainly in $\mathsf{P}$.  Construct the bipartite graph where each vertex $i \in V_1=\{1,2,\ldots,n\}$ is connected to the element(s) $j \in V_2=\{1,2,\ldots,n\}$ such that $|i-j|=A[i]$.  Then the desired permutation $\sigma$ exists if and only if the graph has a perfect matching (i.e., a matching with $n$ edges), which can be determined in polynomial time.