$NP$-completeness of recognizing the difference of two permutations
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.