You are given an array arr[] of size N.
The array consists of a permutation of the set {1, 2, 3, … , N} for some positive integer N. You have to start at the position which has 1 in the array and then travel to the position which has 2. Then from 2, you travel to 3 and so on till you reach the position which has N.
When you travel from Arr[i] to Arr[j], the distance travelled is | i– j |.
Find the total distance you have to travel to reach N when you start from 1.
Example 1:
Input:
N = 5
Arr[] = {5, 1, 4, 3, 2}
Output: 7
Explanation: The numbers and their respective 
indices are given below:
1->1
2->4
3->3
4->2
5->0
Total distance =|4-1|+|3-4|+|2-3|+|0-2| 
= 3+1+1+2 = 7.
Example 2:
Input:
N = 6
Arr[] = {6, 5, 1, 2, 4, 3}
Output: 8
Explanation: 
Total distance = |2-3|+|3-5|+|5-4|+|4-1|+|1-0| 
= 1+2+1+3+1 = 8.
Your Task:
You don't need to read input or print anything. Your task is to complete the function distance() which takes the array of integers arr[] and its size n as input parameters and returns the total distance.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 10^{7}
1<= Arr_{i }<= N

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def distance(self, arr, n):

        # code here

Solutions:
class Solution:

	def distance(self, arr, n):
		di = {}
		for i in range(n):
			di[arr[i]] = i
		su = 0
		for i in range(1, n):
			su += abs(di[i] - di[i + 1])
		return su


class Solution:

	def distance(self, arr, n):
		idc = {}
		for i in range(n):
			idc[arr[i]] = i
		total = 0
		for i in range(1, n):
			total += abs(idc[i] - idc[i + 1])
		return total


class Solution:

	def distance(self, arr, n):
		a = []
		for i in range(n):
			a.append(i)
		res = dict(zip(arr, a))
		a = list(res.values())
		s = 0
		for i in range(len(a) - 1):
			s += abs(a[i + 1] - a[i])
		return s


class Solution:

	def distance(self, arr, n):
		dict_ = {}
		s = 0
		for index in range(n):
			dict_.update({arr[index]: index})
		for index in range(1, n):
			s += abs(dict_[index] - dict_[index + 1])
		return s


class Solution:

	def distance(self, arr, n):
		indexes = [0] * (n + 1)
		dist = 0
		for i in range(n):
			indexes[arr[i]] = i
		for i in range(2, n + 1):
			dist += abs(indexes[i] - indexes[i - 1])
		return dist


class Solution:

	def distance(self, arr, n):
		d = {}
		for i in range(n):
			d[arr[i]] = i
		summ = 0
		for i in range(1, n):
			summ += abs(d[i] - d[i + 1])
		return summ


class Solution:

	def distance(self, arr, n):
		a = dict()
		for i in range(0, n):
			a[arr[i]] = i
		dist = 0
		for i in range(1, n):
			dist = dist + abs(a[i] - a[i + 1])
		return dist


class Solution:

	def distance(self, arr, n):
		d = {}
		for j in range(0, n):
			d[arr[j]] = j
		s = 0
		for j in range(1, n):
			s = s + abs(d[j + 1] - d[j])
		return s


class Solution:

	def distance(self, arr, n):
		di = {}
		for i in range(n):
			di[arr[i]] = i
		sum = 0
		for i in range(1, len(arr)):
			sum = sum + abs(di[i] - di[i + 1])
		return sum


class Solution:

	def distance(self, arr, n):
		d = {}
		diff = 0
		for (ind, val) in enumerate(arr):
			d[val] = ind
		for i in range(1, n):
			diff += abs(d[i] - d[i + 1])
		return diff


class Solution:

	def distance(self, arr, n):
		dict1 = {}
		for i in range(n):
			dict1[arr[i]] = i
		sum = 0
		for i in range(1, n):
			sum += abs(dict1[i] - dict1[i + 1])
		return sum


class Solution:

	def distance(self, arr, n):
		idx = [0] * (n + 1)
		for i in range(n):
			idx[arr[i]] = i
		s = 0
		for i in range(1, n):
			s += abs(idx[i + 1] - idx[i])
		return s


class Solution:

	def distance(self, arr, n):
		dic = {}
		for i in range(n):
			dic[arr[i]] = i
		ele = 1
		dis = 0
		while ele < n:
			dis += abs(dic[ele] - dic[ele + 1])
			ele += 1
		return dis


class Solution:

	def distance(self, arr, n):
		count = 0
		ar = [0] * n
		for i in range(n):
			if arr[i] == n:
				ar[n - 1] = i
			else:
				ar[arr[i] - 1] = i
		for i in range(n - 1):
			count += abs(ar[i] - ar[i + 1])
		return count


class Solution:

	def distance(self, arr, n):
		r = {}
		res = 0
		for x in range(n):
			r[arr[x]] = x
		r1 = [x for x in r.values()]
		for x in range(len(r1) - 1):
			res += abs(r1[x] - r1[x + 1])
		return res


class Solution:

	def distance(self, arr, n):
		temp = [-1] * n
		for i in range(n):
			pos = arr[i] - 1
			data = i
			temp[pos] = data
		distance = 0
		for i in range(n - 1):
			distance += abs(temp[i] - temp[i + 1])
		return distance


class Solution:

	def distance(self, arr, n):
		ans = [0] * n
		for i in range(0, n):
			ans[arr[i] - 1] = i
		tot = 0
		for i in range(0, n - 1):
			tot = tot + abs(ans[i] - ans[i + 1])
		return tot


class Solution:

	def distance(self, arr, n):
		b = [0] * n
		for i in range(n):
			if arr[i] == n:
				b[n - 1] = i
			else:
				b[arr[i] - 1] = i
		s = 0
		for i in range(n - 1):
			s += abs(b[i] - b[i + 1])
		return s
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.distance(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def distance(self, arr, n):
		freq = {}
		for i in range(n):
			freq[arr[i]] = i
		arr.sort()
		sum = 0
		for i in range(1, n):
			sum += abs(freq[arr[i - 1]] - freq[arr[i]])
		return sum
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.distance(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def distance(self, arr, n):
		dic = {}
		total = 0
		for itr in range(n):
			dic[arr[itr]] = itr
		for itr in range(1, n):
			total += abs(dic[itr] - dic[itr + 1])
		return total
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.distance(arr, n)
		print(ans)
		tc -= 1


class Solution:

	def distance(self, arr, n):
		b = [0] * n
		for i in range(n):
			if arr[i] == n:
				b[n - 1] = i
			else:
				b[arr[i] - 1] = i
		s = 0
		for i in range(n - 1):
			s = s + abs(b[i] - b[i + 1])
		return s


class Solution:

	def distance(self, arr, n):
		pos = {num: idx for (idx, num) in enumerate(arr)}
		res = sum((abs(pos[i] - pos[i - 1]) for i in range(2, n + 1)))
		return res


from sys import stdin
input = stdin.readline

class Solution:

	def distance(self, arr, n):
		dist_map = [0] * (n + 1)
		for i in range(0, n):
			dist_map[arr[i]] = i
		sum = 0
		for i in range(1, len(dist_map) - 1):
			temp = dist_map[i + 1] - dist_map[i]
			if temp < 0:
				temp = temp * -1
			sum += temp
		return sum


class Solution:

	def distance(self, arr, n):
		dist_map = [0] * (n + 1)
		for i in range(0, n):
			dist_map[arr[i]] = i
		sum = 0
		for i in range(1, len(dist_map) - 1):
			temp = dist_map[i + 1] - dist_map[i]
			if temp < 0:
				temp = temp * -1
			sum += temp
		return sum


class Solution:

	def distance(self, arr, n):
		positions = {num: idx for (idx, num) in enumerate(arr)}
		result = sum((abs(positions[i] - positions[i - 1]) for i in range(2, n + 1)))
		return result


class Solution:

	def distance(self, arr, n):
		sum = 0
		a = {}
		for (e, i) in enumerate(arr):
			a[i] = e
		arr.sort()
		for i in range(n - 1):
			sum = sum + abs(a[arr[i + 1]] - a[arr[i]])
		return sum


class Solution:

	def distance(self, arr, n):
		d = {}
		for i in range(n):
			d[arr[i]] = i
		sk = sorted(d.keys())
		total = 0
		for i in range(0, n - 1):
			total += abs(d[sk[i]] - d[sk[i + 1]])
		return total


class Solution:

	def distance(self, a, n):
		b = [0] * n
		for i in range(n):
			if a[i] == n:
				b[n - 1] = i
			else:
				b[a[i] - 1] = i
		sum = 0
		for i in range(n - 1):
			sum += abs(b[i] - b[i + 1])
		return sum


class Solution:

	def distance(self, arr, n):
		dic = {}
		for (ind, val) in enumerate(arr):
			dic[val] = ind
		s = 0
		for i in range(2, n + 1):
			s += abs(dic[i] - dic[i - 1])
		return s


class Solution:

	def distance(self, arr, n):
		d = {}
		for i in range(n):
			d[arr[i]] = i
		arr.sort()
		j = n - 1
		ans = 0
		while j > 0:
			ans = ans + abs(d[arr[j]] - d[arr[j - 1]])
			j = j - 1
		return ans


class Solution:

	def distance(self, arr, n):
		d = 0
		l1 = [0] * n
		for i in range(n):
			l1[arr[i] - 1] = i
		for j in range(n - 1):
			d = d + abs(l1[j] - l1[j + 1])
		return d


class Solution:

	def distance(self, arr, n):
		count = {}
		c = 0
		for i in range(1, n + 1):
			count[arr[i - 1]] = i - 1
		a = sorted(count.items())
		for j in range(len(a) - 1):
			c += abs(a[j][1] - a[j + 1][1])
		return c


class Solution:

	def distance(self, arr, n):
		gg = {}
		for (j, i) in enumerate(arr):
			gg[i] = j
		ans = 0
		for i in range(1, n):
			ans += abs(gg[i + 1] - gg[i])
		return ans


class Solution:

	def distance(self, arr, n):
		D = {}
		for i in range(n):
			D[i] = arr[i]
		a = sorted(D, key=D.get)
		su = 0
		for i in range(n - 1):
			su += abs(a[i] - a[i + 1])
		return su


class Solution:

	def distance(self, arr, n):
		temp = [0] * n
		res = 0
		for i in range(n):
			temp[arr[i] - 1] = i
		for i in range(n - 1):
			res += abs(temp[i] - temp[i + 1])
		return res


class Solution:

	def distance(self, arr, n):
		prev = [0] * (n + 1)
		total = 0
		for i in range(n):
			if arr[i] < n:
				prev[arr[i] + 1] = i
				if arr[i] == 1:
					prev[arr[i]] = i
		for i in range(n):
			total += abs(prev[arr[i]] - i)
		return total


class Solution:

	def distance(self, arr, n):
		Hash = [x for x in range(0, n)]
		for i in range(n):
			Hash[arr[i] - 1] = i
		distance = 0
		for i in range(n - 1):
			mx = max(Hash[i], Hash[i + 1])
			mn = min(Hash[i], Hash[i + 1])
			distance += mx - mn
		return distance


class Solution:

	def distance(self, arr, n):
		result = 0
		indexRecord = {}
		for i in range(0, n):
			indexRecord[arr[i]] = i
		for i in range(1, n):
			result = result + abs(indexRecord[i + 1] - indexRecord[i])
		return result


class Solution:

	def distance(self, arr, n):
		d = dict()
		for i in range(len(arr)):
			d[arr[i]] = i
		don = dict(sorted(d.items(), key=lambda item: item[1]))
		l = []
		for i in don.values():
			l.append(i)
		res = 0
		for i in range(len(l) - 1):
			res += abs(l[i + 1] - l[i])
		return res