Almost Sorted Permutation

Given a sequence of n distinct numbers a[1..n], we want to sort them in an ascending order. An interesting property of some sequences is that all numbers are almost at their correct position! More formally, the distance between the current position of any value is at most 1 from its correct position in a sorted order. Now, you want to verify whether the input sequence has such a property. Note