Like people, numbers are also friends with each other. Friendliness between any two numbers a and b is defined as the absolute difference between the two. Lower is this number more friendly the numbers are. Now you are given an array of numbers and you are required to find the friendliness of this array. This can be calculated as the sum of the friendliness of each element in the array with its closest friend in the same array. 
Example 1:
Input:
N=3
arr[] = { 4,1,5 }
Output: 5
Explanation: Sum of absolute differences is
            |4-5| + |1-4| + |5-4| = 5
Example 2:
Input:
N=3
arr[] = { 1,1,1 }
Output: 0
Explanation: Sum of absolute differences is 
             |1-1| + |1-1| + |1-1| = 0
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function sumOfMinAbsDifferences() that takes array arr and integer N as parameters and return the value of friendliness for the given array.
Expected Time Complexity: O(NLogN).
Expected Auxiliary Space: O(1).
Constraints:
2 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3

class Solution:
    def sumOfMinAbsDifferences(self,arr,N):
        #code here.
    

Solutions:
class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort()
		s = 0
		for index in range(1, N - 1):
			one = abs(arr[index] - arr[index + 1])
			two = abs(arr[index] - arr[index - 1])
			s += min(one, two)
		s += abs(arr[-1] - arr[-2])
		s += abs(arr[1] - arr[0])
		return s


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort()
		s = 0
		s += abs(arr[0] - arr[1])
		s += abs(arr[n - 1] - arr[n - 2])
		for i in range(1, n - 1):
			s += min(abs(arr[i] - arr[i - 1]), abs(arr[i] - arr[i + 1]))
		return s


class Solution:

	def sumOfMinAbsDifferences(self, arr, n):
		sum = 0
		arr.sort()
		for i in range(n):
			if i == 0:
				sum += abs(arr[0] - arr[1])
			elif i == n - 1:
				sum += abs(arr[n - 1] - arr[n - 2])
			else:
				a = abs(arr[i] - arr[i + 1])
				b = abs(arr[i] - arr[i - 1])
				sum += min(a, b)
		return sum


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		if N == 1:
			return 0
		arr.sort()
		ans = 0
		for i in range(N):
			if i == 0:
				ans += abs(arr[0] - arr[1])
			elif i == N - 1:
				ans += abs(arr[i] - arr[i - 1])
			else:
				ans += min(arr[i] - arr[i - 1], arr[i + 1] - arr[i])
		return ans


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort()
		arr.insert(0, arr[-1])
		arr.append(arr[1])
		return sum((min(abs(arr[i] - arr[i - 1]), abs(arr[i] - arr[i + 1])) for i in range(1, len(arr) - 1)))


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort()
		summa = arr[1] - arr[0] + arr[-1] - arr[-2]
		for i in range(1, N - 1):
			summa += min(arr[i] - arr[i - 1], arr[i + 1] - arr[i])
		return summa


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort()
		s = 0
		for i in range(1, N - 1, 1):
			s1 = arr[i + 1] - arr[i]
			s2 = arr[i] - arr[i - 1]
			s += min(s1, s2)
		s += arr[1] - arr[0]
		s += arr[N - 1] - arr[N - 2]
		return s


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr = sorted(arr)
		diff = 0
		for i in range(0, N):
			if i == 0:
				diff = diff + abs(arr[i] - arr[i + 1])
			elif i == N - 1:
				diff = diff + abs(arr[i] - arr[i - 1])
			else:
				diff = diff + min(abs(arr[i] - arr[i - 1]), abs(arr[i] - arr[i + 1]))
		return diff


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort()
		l = []
		for i in range(N):
			if i == 0:
				l.append(abs(arr[1] - arr[0]))
			elif i == N - 1:
				l.append(abs(arr[N - 1] - arr[N - 2]))
			else:
				m = abs(arr[i] - arr[i - 1])
				n = abs(arr[i + 1] - arr[i])
				l.append(min(m, n))
		return sum(l)


class Solution:

	def sumOfMinAbsDifferences(self, arr, n):
		a.sort()
		sum = 0
		sum += arr[1] - arr[0]
		sum += arr[n - 1] - arr[n - 2]
		for i in range(1, n - 1):
			sum += min(arr[i + 1] - arr[i], arr[i] - arr[i - 1])
		return sum


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort()
		s = abs(a[0] - a[1]) + abs(a[-1] - a[-2])
		for j in range(1, n - 1):
			m1 = abs(a[j] - a[j - 1])
			m2 = abs(a[j + 1] - a[j])
			m = min(m1, m2)
			s += m
		return s


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort()
		ans = 0
		n = len(arr)
		for i in range(1, n - 1):
			ans += min(arr[i] - arr[i - 1], arr[i + 1] - arr[i])
		ans += arr[n - 1] - arr[n - 2]
		ans += arr[1] - arr[0]
		return ans


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort()
		diff = abs(arr[1] - arr[0])
		for i in range(1, N - 1):
			x = min(arr[i] - arr[i - 1], arr[i + 1] - arr[i])
			diff += abs(x)
		diff += abs(arr[N - 1] - arr[N - 2])
		return diff


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		from typing import List

		def quick_sort(a: List[int]) -> List[int]:
			if len(a) < 2:
				return a
			pivot = a[0]
			(greater_than, smaller_than) = ([], [])
			for i in range(1, len(a)):
				if a[i] > pivot:
					greater_than.append(a[i])
				else:
					smaller_than.append(a[i])
			return quick_sort(smaller_than) + [pivot] + quick_sort(greater_than)
		arr1 = quick_sort(arr)
		result = 0
		for i in range(N):
			if i == 0:
				result += abs(arr1[0] - arr1[1])
			elif i == N - 1:
				result += abs(arr1[N - 1] - arr1[N - 2])
			else:
				result += min(abs(arr1[i] - arr1[i - 1]), abs(arr1[i] - arr1[i + 1]))
		return result


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort()
		s = 0
		t = arr[1] - arr[0]
		s += t
		for i in range(1, N - 1):
			t = arr[i + 1] - arr[i]
			f = arr[i] - arr[i - 1]
			if f < t:
				t = f
			s += t
		t = arr[N - 1] - arr[N - 2]
		s += t
		return s


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort()
		sum = 0
		sum += arr[1] - arr[0]
		for i in range(1, N - 1):
			a = arr[i] - arr[i - 1]
			b = arr[i + 1] - arr[i]
			mini = min(a, b)
			sum += mini
		sum += arr[N - 1] - arr[N - 2]
		return sum


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort()
		if N == 2:
			return arr[1] - arr[0] + (arr[-1] - arr[-2])
		elif N > 2:
			sum1 = arr[1] - arr[0] + (arr[-1] - arr[-2])
			for i in range(1, N - 1):
				abs1 = arr[i] - arr[i - 1]
				abs2 = arr[i + 1] - arr[i]
				sum1 += min(abs1, abs2)
			return sum1


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort()
		ans = arr[1] - arr[0]
		for i in range(1, N - 1):
			if arr[i] - arr[i - 1] < arr[i + 1] - arr[i]:
				ans += arr[i] - arr[i - 1]
			else:
				ans += arr[i + 1] - arr[i]
		ans += arr[n - 1] - arr[n - 2]
		return ans


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort()
		z = []
		for i in range(len(arr)):
			if i == 0:
				z.append(abs(arr[0] - arr[1]))
			elif i == len(arr) - 1:
				z.append(abs(arr[i] - arr[i - 1]))
			elif abs(arr[i] - arr[i - 1]) < abs(arr[i] - arr[i + 1]):
				z.append(abs(arr[i] - arr[i - 1]))
			elif abs(arr[i] - arr[i - 1]) >= abs(arr[i] - arr[i + 1]):
				z.append(abs(arr[i] - arr[i + 1]))
		return sum(z)


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort()
		s = abs(arr[0] - arr[1]) + abs(arr[N - 1] - arr[N - 2])
		j = 1
		while j < N - 1:
			x = arr[j]
			y = abs(x - arr[j + 1])
			z = abs(x - arr[j - 1])
			j += 1
			if y >= z:
				s += z
			else:
				s += y
		return s


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort()
		s = 0
		for (j, i) in enumerate(arr):
			if j == 0:
				s += abs(i - arr[j + 1])
			elif j == N - 1:
				s += abs(i - arr[j - 1])
			else:
				temp1 = abs(i - arr[j - 1])
				temp2 = abs(i - arr[j + 1])
				if temp1 < temp2:
					s += temp1
				else:
					s += temp2
		return s


class Solution:

	def sumOfMinAbsDifferences(self, arr, n):
		s = 0
		arr.sort()
		last = abs(arr[n - 1] - arr[n - 2])
		first = abs(arr[0] - arr[1])
		s = last + first
		for i in range(1, n - 1):
			k = abs(arr[i] - arr[i - 1])
			l = abs(arr[i] - arr[i + 1])
			s += min(k, l)
		return s


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort()
		res = 0
		last = abs(arr[N - 1] - arr[N - 2])
		first = abs(arr[0] - arr[1])
		res = first + last
		for i in range(1, N - 1):
			val1 = abs(arr[i] - arr[i - 1])
			val2 = abs(arr[i] - arr[i + 1])
			res += min(val1, val2)
		return res


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort()
		s = 0
		s += abs(arr[0] - arr[1])
		for i in range(1, N - 1):
			c = abs(arr[i] - arr[i + 1])
			e = abs(arr[i] - arr[i - 1])
			s += min(c, e)
		s += arr[n - 1] - arr[n - 2]
		return s
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	ob = Solution()
	ans = ob.sumOfMinAbsDifferences(a, n)
	print(ans)


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort()
		friendliness = abs(arr[1] - arr[0])
		for itr in range(1, n - 1):
			if abs(arr[itr] - arr[itr + 1]) > abs(arr[itr] - arr[itr - 1]):
				friendliness += abs(arr[itr] - arr[itr - 1])
			else:
				friendliness += abs(arr[itr] - arr[itr + 1])
		friendliness += abs(arr[n - 2] - arr[n - 1])
		return friendliness
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	ob = Solution()
	ans = ob.sumOfMinAbsDifferences(a, n)
	print(ans)


class Solution:

	def sumOfMinAbsDifferences(self, a, n):
		a.sort()
		if abs(a[0] - a[1]) <= abs(a[0] - a[n - 1]):
			su = abs(a[0] - a[1])
		else:
			su = abs(a[0] - a[n - 1])
		for i in range(1, n - 1):
			if abs(a[i] - a[i - 1]) <= abs(a[i] - a[i + 1]):
				su = su + abs(a[i] - a[i - 1])
			else:
				su = su + abs(a[i] - a[i + 1])
		if abs(a[n - 1] - a[0]) <= abs(a[n - 1] - a[n - 2]):
			su = su + abs(a[n - 1] - a[0])
		else:
			su = su + abs(a[n - 1] - a[n - 2])
		return su


class Solution:

	def sumOfMinAbsDifferences(self, a, n):
		s = 0
		a.sort()
		for_1st_ele = abs(a[0] - a[1])
		for_last_ele = abs(a[-1] - a[-2])
		s += for_1st_ele
		s += for_last_ele
		for i in range(1, n - 1):
			s += min(abs(a[i] - a[i - 1]), abs(a[i] - a[i + 1]))
		return s


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort(reverse=True)
		total = 0
		for i in range(N):
			right = float('inf')
			left = float('inf')
			if i + 1 < N:
				right = arr[i] - arr[i + 1]
			if i - 1 >= 0:
				left = arr[i - 1] - arr[i]
			total += min(left, right)
		return total


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort()
		k = 0
		for i in range(len(arr)):
			if i == len(arr) - 1:
				s = abs(arr[i] - arr[i - 1])
				k = k + s
			elif i == 0:
				s = abs(arr[i + 1] - arr[i])
				k = k + s
			else:
				s = min(abs(arr[i] - arr[i - 1]), abs(arr[i] - arr[i + 1]))
				k = k + s
		return k


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		if N == 2:
			return 2 * abs(arr[0] - arr[1])
		dict = {}
		new_arr = sorted(arr)
		for i in range(N):
			if i == 0:
				dict[new_arr[i]] = [new_arr[i + 1]]
			elif i == N - 1:
				dict[new_arr[i]] = [new_arr[i - 1]]
			else:
				dict[new_arr[i]] = [new_arr[i + 1], new_arr[i - 1]]
		s = 0
		for i in range(N):
			s += min(abs(max(dict[arr[i]]) - arr[i]), abs(min(dict[arr[i]]) - arr[i]))
		return s


class Solution:

	def sumOfMinAbsDifferences(self, l, n):
		if n == 1:
			return 0
		l.sort()
		ts = l[1] - l[0] + (l[-1] - l[-2])
		for i in range(1, n - 1):
			ts += min(l[i] - l[i - 1], l[i + 1] - l[i])
		return ts


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		total = 0
		arr.sort()
		for a in range(N):
			if a == 0:
				total += abs(arr[0] - arr[1])
			elif a == N - 1:
				total += abs(arr[N - 1] - arr[N - 2])
			else:
				total += min(abs(arr[a] - arr[a - 1]), abs(arr[a] - arr[a + 1]))
		return total


class Solution:

	def sumOfMinAbsDifferences(self, arr, N):
		arr.sort()
		sum = 0
		i = 0
		while i < len(arr):
			if i == len(arr) - 1:
				sum += abs(arr[i] - arr[i - 1])
			elif abs(arr[i] - arr[i + 1]) < abs(arr[i] - arr[i - 1]):
				sum += abs(arr[i] - arr[i + 1])
			else:
				sum += abs(arr[i] - arr[i - 1])
			i += 1
		return sum