Vadim is really keen on travelling. Recently he heard about kayaking activity near his town and became very excited about it, so he joined a party of kayakers.

Now the party is ready to start its journey, but firstly they have to choose kayaks. There are 2·n people in the group (including Vadim), and they have exactly n - 1 tandem kayaks (each of which, obviously, can carry two people) and 2 single kayaks. i-th person's weight is w_{i}, and weight is an important matter in kayaking — if the difference between the weights of two people that sit in the same tandem kayak is too large, then it can crash. And, of course, people want to distribute their seats in kayaks in order to minimize the chances that kayaks will crash.

Formally, the instability of a single kayak is always 0, and the instability of a tandem kayak is the absolute difference between weights of the people that are in this kayak. Instability of the whole journey is the total instability of all kayaks.

Help the party to determine minimum possible total instability! 


-----Input-----

The first line contains one number n (2 ≤ n ≤ 50).

The second line contains 2·n integer numbers w_1, w_2, ..., w_2n, where w_{i} is weight of person i (1 ≤ w_{i} ≤ 1000).


-----Output-----

Print minimum possible total instability.


-----Examples-----
Input
2
1 2 3 4

Output
1

Input
4
1 3 4 6 3 4 100 200

Output
5

Source: codeforces | Difficulty: MEDIUM
Tags: Complete search

Sorting

Greedy algorithms


Solutions:
n = int(input())
w = list(map(int, input().split()))
ans = []
w.sort()
ans = float('inf')
n *= 2
for i in range(n - 1):
	for j in range(i + 1, n):
		cur = 0
		a = list(w[:i] + w[i + 1:j] + w[j + 1:])
		for k in range(0, len(a) - 1, 2):
			cur += a[k + 1] - a[k]
		ans = min(ans, cur)
print(ans)


def get_instability(w, x, y):
	total = 0
	last = -1
	for i in range(len(w)):
		if i == x or i == y:
			continue
		if last == -1:
			last = w[i]
		else:
			total += w[i] - last
			last = -1
	return total

def main():
	n = int(input())
	weights = sorted(list(map(int, input().split())))
	min_instability = 1 << 30
	for i in range(2 * n):
		for j in range(i + 1, 2 * n):
			instability = get_instability(weights, i, j)
			if instability < min_instability:
				min_instability = instability
	print(min_instability)
main()


n = int(input())
weights = [int(i) for i in input().split()]
weights.sort()
total_instability = []
for i in range(len(weights) - 1):
	a = weights[i]
	for j in range(i + 1, len(weights)):
		instability = 0
		try:
			b = weights[j]
			weights.remove(a)
			weights.remove(b)
			for k in range(0, len(weights), 2):
				instability += weights[k + 1] - weights[k]
			weights.append(a)
			weights.append(b)
			weights.sort()
		except:
			pass
		total_instability.append(instability)
print(min(total_instability))


n = int(input())
weights = [int(i) for i in input().split()]
weights.sort(reverse=True)
possibleOutputs = set()
for x in range(2 * n):
	for y in range(x, 2 * n):
		if x != y:
			tempList = []
			for i in range(2 * n):
				if i != x:
					if i != y:
						tempList.append(weights[i])
			possibleOutputs.add(sum([tempList[2 * i] - tempList[2 * i + 1] for i in range(n - 1)]))
print(min(possibleOutputs))


input()
l = list(map(int, input().split()))
l.sort()
count = 100000
for i in range(len(l)):
	for j in range(i + 1, len(l)):
		l_new = l[:]
		l_new.pop(j)
		l_new.pop(i)
		v = sum([abs(l_new[k] - l_new[k + 1]) for k in range(0, len(l_new), 2)])
		if v < count:
			count = v
print(count)


n = int(input())
l = list(map(int, input().split()))
nat = False
for i in range(2 * n):
	for c in range(i + 1, 2 * n):
		ls = l[:]
		ls[i] = 0
		ls[c] = 0
		ls = sorted(ls)
		now = 0
		for loc in range(1, len(ls), 2):
			now += ls[loc] - ls[loc - 1]
		if now < nat or str(nat) == 'False':
			nat = now
print(nat)


from itertools import combinations, chain
from math import inf

def take(s):
	return sum([abs(next(s) - next(s)) for _ in range(n - 1)])
n = int(input())
wi = sorted(map(int, input().split()))
minimum = inf
for lonely_couple in combinations(range(2 * n), 2):
	sample = chain(wi[:lonely_couple[0]], wi[lonely_couple[0] + 1:lonely_couple[1]], wi[lonely_couple[1] + 1:])
	minimum = min(minimum, take(sample))
print(minimum)


n = int(input())
arr = [int(z) for z in input().split()]
arr.sort()
ans = 10 ** 18
for i in range(2 * n - 1):
	for j in range(i + 1, 2 * n):
		arr1 = []
		for k in range(2 * n):
			if k != i and k != j:
				arr1.append(arr[k])
		a = 0
		for l in range(0, 2 * n - 2, 2):
			a += arr1[l + 1] - arr1[l]
		ans = min(ans, a)
print(ans)


n = int(input())
p = list(map(int, input().split()))
p.sort()
temp = 0
ans = 10 ** 10
for i in range(2 * n):
	for j in range(i + 1, 2 * n):
		s = 0
		for k in range(2 * n):
			if k != i and k != j:
				if temp == 0:
					temp = p[k]
				else:
					s += abs(temp - p[k])
					temp = 0
		ans = min(ans, s)
print(ans)


n = int(input())
n = 2 * n
w = [int(i) for i in input().split()]
w.sort()
import math
res = math.inf
for x in range(n):
	for y in range(x + 1, n):
		wc = w[:]
		wc.pop(y)
		wc.pop(x)
		s = 0
		for i in range(0, n - 3, 2):
			s += wc[i + 1] - wc[i]
		res = min(s, res)
print(res)


n = int(input())
s = list(map(int, input().split()))
s = list(sorted(s))
ansm = 100000000
for i in range(len(s)):
	s1 = s[:i] + s[i + 1:]
	for j in range(len(s1)):
		s2 = s1[:j] + s1[j + 1:]
		ans = 0
		for i in range(1, 2 * n - 2, 2):
			ans += s2[i] - s2[i - 1]
		if ans < ansm:
			ansm = ans
print(ansm)


n = 2 * int(input())
w = sorted(map(int, input().split()))
r = 10000
for i in range(n):
	for j in range(i):
		u = w[:j] + w[j + 1:i] + w[i + 1:]
		r = min(r, sum((u[i + 1] - u[i] for i in range(0, n - 3, 2))))
print(r)


n = int(input())
l = [int(i) for i in input().split()]
l.sort()
mini = 10 ** 100
for i in range(2 * n):
	for j in range(0, 2 * n):
		inst = 0
		l1 = []
		for k in range(2 * n):
			if k == i or k == j:
				continue
			l1.append(l[k])
		l1.sort()
		for x in range(1, len(l1), 2):
			inst += l1[x] - l1[x - 1]
		mini = min(mini, inst)
print(mini)


def main():
	nK = int(input()) - 1
	wL = list(map(int, input().split()))
	wL = sorted(wL)
	ans = findScore(wL)
	print(ans)

def findScore(wL):
	scoreL = []
	for i in range(len(wL) - 1):
		for j in range(i + 1, len(wL)):
			temp = wL.copy()
			temp.pop(temp.index(wL[i]))
			temp.pop(temp.index(wL[j]))
			n = 0
			score1 = 0
			for k in range(len(temp) // 2):
				score1 += temp[n + 1] - temp[n]
				n += 2
			scoreL.append(score1)
	return min(scoreL)
ans = main()


n = int(input())
val = list(map(int, input().split()))
val.sort()
b_a = 10 ** 9
for i in range(len(val) - 1):
	for j in range(i + 1, len(val)):
		if i == j:
			continue
		ans = 0
		(a, b) = (val[i], val[j])
		val.pop(j)
		val.pop(i)
		ans = 0
		for k in range(len(val)):
			if k % 2 == 0:
				ans += abs(val[k + 1] - val[k])
		b_a = min(b_a, ans)
		val.insert(i, a)
		val.insert(j, b)
print(b_a)


n = int(input())
weights = input().split()
weights = [int(w) for w in weights]
min_ans = float('inf')
perm = list(weights)
perm.sort()
for i in range(0, len(perm)):
	for j in range(i, len(perm)):
		if i == j:
			continue
		weights = list(perm)
		weights.pop(max(i, j))
		weights.pop(min(i, j))
		diff = []
		for k in range(0, len(weights) - 1, 2):
			diff.append(weights[k + 1] - weights[k])
		ans = sum(diff)
		min_ans = min(min_ans, ans)
print(min_ans)


n = int(input())
t = list(map(int, input().split()))
t.sort()
ans = 10000000000000
n *= 2
for i in range(n - 1):
	for j in range(i + 1, n):
		temp = 0
		s = list(t[:i] + t[i + 1:j] + t[j + 1:])
		for k in range(1, len(s), 2):
			temp += s[k] - s[k - 1]
		ans = min(ans, temp)
print(ans)


n = int(input())
l = list(map(int, input().split()))
from itertools import combinations
from copy import deepcopy
answ = []
for i in combinations(l, 2):
	ls = deepcopy(l)
	for j in i:
		ls.remove(j)
	ls.sort()
	ans = 0
	for i in range(0, len(ls) - 1, 2):
		ans += ls[i + 1] - ls[i]
	answ.append(ans)
print(min(answ))


n = int(input())
a = list(map(int, input().strip().split()))
a.sort()
best = 100000
for i in range(0, 2 * n - 1):
	for j in range(i + 1, 2 * n):
		diff = 0
		p = -1
		for k in range(0, 2 * n):
			if k != i and k != j:
				diff += p * a[k]
				p = -p
		best = min(best, diff)
print(best)


import sys
n = int(input()) * 2
a = sorted(map(int, input().split()))
ans = 10 ** 9
for ex1 in range(n):
	for ex2 in range(ex1 + 1, n):
		(i, j) = (0, 0)
		res = 0
		while i < n:
			while i < n and (i == ex1 or i == ex2):
				i += 1
			j = i + 1
			while j < n and (j == ex1 or j == ex2):
				j += 1
			if j >= n:
				break
			res += abs(a[i] - a[j])
			i = j + 1
		ans = min(ans, res)
print(ans)


import math
n = int(input())
a = list(map(int, input().split()))
a.sort()
x = []
ans = math.inf
for t in range(2 * n):
	for k in range(t, 2 * n):
		c = a[:]
		c = a[:t] + a[t + 1:k] + a[k + 1:]
		for i in range(0, 2 * n - 2, 2):
			x.append(c[i + 1] - c[i])
		ans = min(ans, sum(x))
		x = []
print(ans)


n = int(input())
arr = list(map(int, input().split(' ')))
arr.sort()
dif_list = []
for i in arr:
	for j in arr:
		k = 0
		count = 0
		copyarr = arr.copy()
		if i == j:
			continue
		copyarr.remove(i)
		copyarr.remove(j)
		while k < 2 * n - 2:
			count += abs(copyarr[k] - copyarr[k + 1])
			k += 2
		dif_list.append(count)
print(min(dif_list))


n = int(input())
w = list(map(int, input().split()))
w.sort()
swd = [0, 0]
for i in range(n * 2 - 1):
	swd.append(swd[i] + (w[i + 1] - w[i]))
m = swd[n * 2]
for i in range(n):
	for j in range(0, n - i):
		s = swd[i * 2] + swd[(i + j) * 2 + 1] - swd[i * 2 + 1] + swd[n * 2] - swd[(i + j + 1) * 2]
		if s < m:
			m = s
print(m)


def calcdifs(nums):
	difs = []
	for i in range(len(nums) - 1):
		difs.append(nums[i + 1] - nums[i])
	return sum(difs[::2])
input()
nums = sorted([int(x) for x in input().split()])
allvalues = []
for (i, ii) in enumerate(nums):
	for (j, jj) in enumerate(nums):
		if i != j:
			nums2 = nums.copy()
			nums2.remove(ii)
			nums2.remove(jj)
			allvalues.append(calcdifs(nums2))
print(min(allvalues))


n = int(input())
nums = list(map(int, input().strip().split()))
weight = sorted(nums)
min_total = sum(weight)
for i in range(0, 2 * n - 1):
	for j in range(i + 1, 2 * n):
		nums_tmp = []
		for k in range(2 * n):
			if k != i and k != j:
				nums_tmp.append(weight[k])
		total = 0
		for k in range(n - 1):
			total += nums_tmp[2 * k + 1] - nums_tmp[2 * k]
		if total < min_total:
			min_total = total
print(min_total)


n = int(input())
ln = n * 2
weight = input()
weight = weight.split(' ')
length = len(weight)
weight = list(map(int, weight))
arr = []
sum = 0
mini = 50000000000
for l in range(0, ln):
	for k in range(l + 1, ln):
		arr = []
		sum = 0
		for i in range(0, ln):
			if i != l and i != k:
				arr.append(weight[i])
		arr.sort()
		for i in range(0, ln - 2, 2):
			sum = sum + arr[i + 1] - arr[i]
		if mini > sum:
			mini = sum
print(mini)


input()
w = list(map(int, input().split()))
w = sorted(w)
if len(w) % 2 == 0:
	minsum = 10 ** 10
	for a in range(len(w)):
		for b in range(a + 1, len(w)):
			sum = 0
			p = w[:a] + w[a + 1:b] + w[b + 1:]
			for c in range(len(p) // 2):
				sum += p[2 * c + 1] - p[2 * c]
			if sum < minsum:
				minsum = sum
	print(minsum)


n = int(input())
w = list(map(int, input().split()))
w.sort()
ans = []
for i in range(n * 2):
	for j in range(i + 1, n * 2):
		a = w[:i] + w[i + 1:j] + w[j + 1:]
		ans.append(abs(sum(a[1::2]) - sum(a[::2])))
print(min(ans))


def vals(i, j, L):
	for x in range(len(L)):
		if x not in (i, j):
			yield L[x]

def pairs(i, j, L):
	s = []
	for x in vals(i, j, L):
		s.append(x)
		if len(s) == 2:
			yield s
			s = []

def summa(i, j, L):
	count = 0
	for (a, b) in pairs(i, j, L):
		count += abs(a - b)
	return count

def main():
	input()
	L = [int(i) for i in input().split()]
	L.sort()
	mini = 10 ** 100
	for i in range(len(L)):
		for j in range(i + 1, len(L)):
			mini = min(mini, summa(i, j, L))
	print(mini)
main()


import sys

def main(pname):
	n = int(input())
	l = [int(i) for i in input().split()]
	l.sort()
	m = 100000
	for i in range(2 * n):
		for j in range(i):
			d = l[:j] + l[j + 1:i] + l[i + 1:]
			s = 0
			for k in range(0, len(d) - 1, 2):
				s += d[k + 1] - d[k]
			m = min(m, s)
	print(m)
main('1164')


n = int(input())
w = list(map(int, input().split()))
w.sort()
ans = 50000
for i in range(2 * n - 1):
	for j in range(i + 1, 2 * n):
		tmp = 0
		for k in range(2 * n):
			if k < i or j < k:
				if k % 2 == 0:
					tmp -= w[k]
				else:
					tmp += w[k]
			elif i < k < j:
				if k % 2 == 1:
					tmp -= w[k]
				else:
					tmp += w[k]
		ans = min(ans, tmp)
print(ans)


n = int(input())
ws = sorted(list(map(int, input().split())))
ans = []
for i in range(len(ws)):
	for j in range(i + 1, len(ws)):
		b = ws[:i] + ws[i + 1:j] + ws[j + 1:]
		s = sum(b[1::2]) - sum(b[::2])
		ans.append(s)
print(min(ans))


n = int(input())
w = list(map(int, input().split()))
w.sort()
instability = list()
for i in range(2 * n):
	for j in range(i + 1, 2 * n):
		cnt = 0
		for k in range(2 * n):
			if k < i or k > j:
				if k % 2 == 0:
					cnt -= w[k]
				else:
					cnt += w[k]
			if k > i and k < j:
				if k % 2 == 0:
					cnt += w[k]
				else:
					cnt -= w[k]
		instability.append(cnt)
print(min(instability))


n = int(input())
arr = [int(el) for el in input().split()]
arr.sort()
d_rez = []
m = 99999999
l = len(arr)
for i in range(0, l - 1):
	for j in range(i + 1, l):
		a = arr.pop(i)
		b = arr.pop(j - 1)
		size = l - 2
		diff = []
		s = 0
		for h in range(0, size, 2):
			s = s + arr[h + 1] - arr[h]
		if s < m:
			m = s
			d_rez = arr
		arr.append(a)
		arr.append(b)
		arr.sort()
print(m)


n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 10 ** 9
for i in range(2 * n - 1):
	for j in range(i + 1, 2 * n):
		s = 0
		last = -1
		for k in range(2 * n):
			if k == j or k == i:
				continue
			if last == -1:
				last = a[k]
			else:
				s += a[k] - last
				last = -1
		ans = min(ans, s)
print(ans)


def insertionSort(myList):
	for i in range(1, len(myList)):
		currentIndex = i
		while myList[currentIndex] < myList[currentIndex - 1]:
			temp = myList[currentIndex - 1]
			myList[currentIndex - 1] = myList[currentIndex]
			myList[currentIndex] = temp
			currentIndex = currentIndex - 1
			if currentIndex == 0:
				break
	return myList
n = int(input())
weightList = input()
weightList = list(weightList.split(' '))
for i in range(len(weightList)):
	weightList[i] = int(weightList[i])
weightList = insertionSort(weightList)
minInstability = 9999999
for i in range(len(weightList)):
	for k in range(i + 1, len(weightList)):
		skipped = 0
		instability = 0
		for j in range(len(weightList) - 2):
			if j + skipped == i:
				skipped = 1
			if j + skipped == k:
				skipped = 2
			if j % 2 == 0:
				instability = instability - weightList[j + skipped]
			else:
				instability = instability + weightList[j + skipped]
		if instability < minInstability:
			minInstability = instability
print(minInstability)


INF = 1061109567
n = int(input())
t = n - 1
n = n + n
str = input()
ls = [int(x) for x in str.split()]
ls.sort()
x = []
ans = INF
for i in range(0, n):
	for j in range(i + 1, n):
		x = []
		sum = 0
		for k in range(n):
			if i != k and j != k:
				x.append(ls[k])
		for k in range(t):
			sum += x[k * 2 + 1] - x[k * 2]
		ans = min(ans, sum)
print(ans)


diffs = int(input())
weights1 = sorted(list(map(int, input().split())))
instabilities = []
for x in range(len(weights1)):
	for y in range(len(weights1) - 1):
		weights2 = weights1[:]
		weights2.pop(x)
		weights2.pop(y)
		instability = 0
		for i in range(diffs - 1):
			val = 99999999
			for j in range(len(weights2) - 1):
				if weights2[j + 1] - weights2[j] < val:
					val = weights2[j] - weights2[j + 1]
					posRem1 = j + 1
					posRem2 = j
			weights2.pop(posRem1)
			weights2.pop(posRem2)
			instability += abs(val)
		instabilities.append(instability)
print(min(instabilities))


def get_ints():
	return [int(n) for n in input().split()]

def get_floats():
	return [float(n) for n in input().split()]

def calc(w, rid):
	plus = True
	val = 0
	for (i, t) in enumerate(w):
		if i not in rid:
			if plus:
				val += t
			else:
				val -= t
			plus = not plus
	return val
a = get_ints()
assert len(a) == 1
n = a[0]
count = 2 * n
w = get_ints()
assert len(w) == count
w.sort(reverse=True)
best = list()
for i in range(count):
	for j in range(i + 1, count):
		best.append(calc(w, [i, j]))
print(min(best))


n = int(input())
l = list(map(int, input().split()))
l.sort()
m = 50000
s = 0
for i in range(0, 2 * n):
	for j in range(i + 1, 2 * n):
		s = 0
		k = 0
		l1 = []
		while k < 2 * n:
			if k != i and k != j:
				l1.append(l[k])
			k += 1
		for k in range(0, len(l1), 2):
			s += l1[k + 1] - l1[k]
		m = min(s, m)
print(m)


n = int(input())
lst = [*map(int, input().split())]
lst.sort()
item = n * 2 - 2
res = 100000000000000000000000000
for (i, x) in enumerate(lst):
	for (j, y) in enumerate(lst):
		if i != j:
			mas = lst[:]
			mas.pop(i)
			mas.pop(j - 1)
			result = 0
			for k in range(0, item, 2):
				result += mas[k + 1] - mas[k]
			res = min(res, result)
print(res)


n = int(input())
w = list(map(int, input().split()))
h = dict()
for val in w:
	h[val] = h.get(val, 0) + 1
res = []
for key in h:
	res += [key] * (h[key] % 2)
res.sort()
s = []
for i in range(len(res)):
	for j in range(i + 1, len(res)):
		b = res[:i] + res[i + 1:j] + res[j + 1:]
		s.append(abs(sum(b[::2]) - sum(b[1::2])))
print(min(s))


n = int(input())
w = list(map(int, input().split()))
w.sort()
d = []
for i in range(0, 2 * n):
	for j in range(i + 1, 2 * n):
		if i == j:
			continue
		tw = list(w)
		tw.pop(i)
		tw.pop(j - 1)
		td = 0
		for k in range(0, len(tw), 2):
			td += tw[k + 1] - tw[k]
		d.append(td)
print(min(d))


def solve():
	n = int(input())
	w = [int(st) for st in input().split(' ')]
	w.sort()
	ans = 2 ** 31
	(ansi, ansj) = (None, None)
	for i in range(0, 2 * n - 1, 2):
		for j in range(i + 1, 2 * n, 2):
			s = 0
			for k in range(0, i - 1, 2):
				s += w[k + 1] - w[k]
			for k in range(i + 1, j - 1, 2):
				s += w[k + 1] - w[k]
			for k in range(j + 1, 2 * n - 1, 2):
				s += w[k + 1] - w[k]
			if s < ans:
				ans = s
				ansi = i
				ansj = j
	return ans
print(solve())


n = int(input())
a = sorted(list(map(int, input().split())))
x = 10 ** 20
for i in range(2 * n):
	for j in range(i + 1, 2 * n):
		(s, l, r) = (0, 0, 1)
		while l < 2 * n - 1:
			while l == i or l == j:
				l += 1
			r = l + 1
			while r == i or r == j:
				r += 1
			if r >= 2 * n:
				break
			s += abs(a[r] - a[l])
			l = r + 1
		x = min(s, x)
print(x)


n = int(input())
l = sorted(list(map(int, input().split())))
res = 10000000000000000
for i in range(2 * n):
	for j in range(i + 1, 2 * n):
		l1 = [l[k] for k in range(2 * n) if k != i and k != j]
		res = min(res, sum([l1[k + 1] - l1[k] for k in range(0, 2 * n - 2, 2)]))
print(res)


def codeforces(numbers):
	results = []
	numbers.sort()
	for i in range(len(numbers)):
		for j in range(len(numbers)):
			if i == j:
				continue
			nums = [numbers[indx] for indx in range(len(numbers)) if indx not in [i, j]]
			results.append(calculate(nums))
	return min(results)

def calculate(numbers):
	result = 0
	for indx in range(0, len(numbers), 2):
		result += abs(numbers[indx + 1] - numbers[indx])
	return result
_ = input()
numbers = list(map(int, input().split()))
print(codeforces(numbers))


def diff(arr):
	ans = []
	for i in range(1, len(arr), 2):
		ans.append(arr[i] - arr[i - 1])
	return sum(ans)
n = int(input())
a = list(map(int, input().split()))
a.sort()
real_ans = []
for i in range(2 * n - 1):
	for j in range(i + 1, 2 * n):
		b = a.copy()
		b.pop(i)
		b.pop(j - 1)
		real_ans.append(diff(b))
print(min(real_ans))


def list_input():
	return list(map(int, input().split()))

def map_input():
	return map(int, input().split())

def map_string():
	return input().split()
n = int(input())
n *= 2
a = list_input()
a.sort()
ans = 10000000000000
for i in range(n):
	for j in range(i + 1, n):
		b = []
		for k in range(n):
			if k != i and k != j:
				b.append(a[k])
		cur = 0
		for k in range(0, n - 2, 2):
			cur += b[k + 1] - b[k]
		ans = min(ans, cur)
print(ans)


N = int(input())
Kayak = {}
for i in [int(i) for i in input().split()]:
	if i in Kayak and Kayak[i] == 1:
		del Kayak[i]
	else:
		Kayak[i] = 1
k = list(Kayak.keys())
k.sort()

def func(li):
	result = 0
	for i in range(int(len(li) / 2)):
		result += abs(li[2 * i] - li[2 * i + 1])
	return result
mi = 1000
if len(k) <= 2:
	print(0)
else:
	for i in range(len(k) - 1):
		for i2 in range(i + 1, len(k)):
			kc = k.copy()
			numi = k[i]
			numi2 = k[i2]
			kc.remove(numi)
			kc.remove(numi2)
			mi = min(mi, func(kc))
	print(mi)


def readln():
	return map(int, input().rstrip().split())

def cal(dt):
	rs = 0
	for i in range(len(dt) // 2):
		rs += abs(dt[2 * i] - dt[2 * i + 1])
	return rs
n = int(input())
data = list(readln())
data.sort()
minw = 500000
for i in range(0, 2 * n - 1):
	for j in range(i + 1, 2 * n):
		dt = list(data)
		dt.pop(max(i, j))
		dt.pop(min(i, j))
		rs = cal(dt)
		if rs < minw:
			minw = rs
print(minw)


n = int(input())
n = n * 2
arr = sorted(map(int, input().split()))
x = arr[n - 1]
for i in range(n):
	for j in range(i):
		(a, h, q) = (0, 0, 0)
		while h < n:
			if h == i or h == j:
				pass
			else:
				if q % 2 == 0:
					a -= arr[h]
				else:
					a += arr[h]
				q += 1
			h += 1
		x = min(x, a)
print(x)


n = int(input()) * 2
w = [int(x) for x in input().split()]
w.sort(reverse=True)
a = [0] * n
s = 10 ** 100
for i in range(n - 1):
	for j in range(i + 1, n):
		b = []
		for k in range(n):
			if k != i and k != j:
				b.append(w[k])
		for k in range(0, n - 3, 2):
			a[k] = abs(b[k] - b[k + 1])
		s = min(s, sum(a))
print(s)


n = int(input())
w = list(map(int, input().split()))
w.sort()
stab1 = 0
stab2 = 0
stab3 = 0
stabmin = 99999999999999999
for i in range(2 * n):
	for j in range(i + 1, 2 * n):
		temp = w.copy()
		del temp[i]
		del temp[j - 1]
		stab1 = 0
		for k in range(n - 1):
			stab1 += temp[2 * k + 1] - temp[2 * k]
		stabmin = min(stab1, stabmin)
print(stabmin)


n = 2 * int(input())
arr = sorted(map(int, input().split()))
x = arr[n - 1]
for i in range(n):
	for j in range(i):
		u = arr[:j] + arr[j + 1:i] + arr[i + 1:]
		a = sum((u[h + 1] - u[h] for h in range(0, n - 3, 2)))
		x = min(x, a)
print(x)


n = int(input())
weights = input().strip().split()
for weight in range(len(weights)):
	weights[weight] = int(weights[weight])
weights.sort()
reset = weights[:]
totalList = []
for exclude1 in range(len(weights) - 1):
	for exclude2 in range(exclude1 + 1, len(weights)):
		reset = weights[:]
		total = 0
		reset.pop(exclude2)
		reset.pop(exclude1)
		for weight in range(0, len(reset), 2):
			total += reset[weight + 1] - reset[weight]
		totalList.append(total)
print(min(totalList))


import sys, math, queue, bisect
MOD = 10 ** 9 + 7
sys.setrecursionlimit(1000000)
n = int(input())
a = sorted(map(int, input().split()))
ans = 10 ** 10
for i in range(2 * n):
	for j in range(i + 1, 2 * n):
		b = []
		for k in range(2 * n):
			if k == i or k == j:
				continue
			b.append(a[k])
		b = sum([abs(b[i] - b[i - 1]) for i in range(1, len(b), 2)])
		ans = min(ans, b)
print(ans)


def total_insta(www, exl1, exl2):
	wwe = www[:]
	wwe.remove(exl1)
	wwe.remove(exl2)
	result = 0
	for x in range(len(wwe) // 2):
		result += abs(wwe[x * 2] - wwe[x * 2 + 1])
	return result

class CodeforcesTask863BSolution:

	def __init__(self):
		self.result = ''
		self.n = 0
		self.weights = []

	def read_input(self):
		self.n = int(input())
		self.weights = [int(x) for x in input().split(' ')]

	def process_task(self):
		self.weights.sort()
		mnx = sum(self.weights)
		for x in range(self.n * 2):
			for y in range(self.n * 2):
				if x != y:
					mnx = min(mnx, total_insta(self.weights, self.weights[x], self.weights[y]))
		self.result = str(mnx)

	def get_result(self):
		return self.result
Solution = CodeforcesTask863BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


n = int(input())
w = list(map(int, input().split()))
w.sort()
ans = []
v = []
for i in range(len(w)):
	for j in range(i + 1, len(w)):
		v = w[:i] + w[i + 1:j] + w[j + 1:]
		s = 0
		for c in range(0, len(v), 2):
			s += v[c]
		for g in range(1, len(v), 2):
			s = s - v[g]
		ans.append(abs(s))
print(min(ans))


ct = int(input())
weights = sorted(list(map(int, input().split())))
ultidiffs = []
for j in range(2 * ct):
	for i in range(2 * ct):
		if i != j:
			diffs = []
			new_weights = []
			for k in range(2 * ct):
				if k != i and k != j:
					new_weights.append(weights[k])
			for l in range(len(new_weights) // 2):
				diffs.append(abs(new_weights[2 * l] - new_weights[2 * l + 1]))
			ultidiffs.append(sum(diffs))
print(min(ultidiffs))


n = int(input())
w = sorted([int(x) for x in input().split()])
best = 999999999999
for ex1 in range(1, n * 2):
	for ex2 in range(0, ex1):
		prev = -1
		sum = 0
		for i in range(0, n * 2):
			if i == ex1 or i == ex2:
				continue
			if prev == -1:
				prev = w[i]
			else:
				sum += w[i] - prev
				prev = -1
		best = min(best, sum)
print(best)


from collections import Counter, defaultdict

def solve(weights, n):
	weights = sorted(weights)
	tandem_kayaks = n - 1
	single_kayak = 2
	ans = 0
	ctr = Counter(weights)
	for (k, v) in ctr.items():
		(q, r) = divmod(v, 2)
		ctr[k] = r
	remaining = []
	for (k, v) in ctr.items():
		if v > 0:
			remaining += [k] * v
	hmap = defaultdict(int)
	for i in range(0, len(remaining) - 1):
		diff = abs(remaining[i] - remaining[i + 1])
		hmap[i, i + 1] = diff
	visited = set()
	hmap = {k: v for (k, v) in sorted(hmap.items(), key=lambda x: x[1])}
	rl = len(remaining)
	for (k, v) in hmap.items():
		(a, b) = k
		if rl <= 2:
			break
		if a not in visited and b not in visited:
			ans += v
			visited.add(a)
			visited.add(b)
			rl -= 2
	print(ans)

def solve2(l, n):
	from itertools import combinations
	from copy import deepcopy
	answ = []
	for c in combinations(l, 2):
		ls = deepcopy(l)
		for j in c:
			ls.remove(j)
		ls.sort()
		ans = 0
		for i in range(0, len(ls) - 1, 2):
			ans += ls[i + 1] - ls[i]
		answ.append(ans)
	print(min(answ))
n = int(input())
weights = list(map(int, input().split()))
solve2(weights, n)


n = int(input())
a = list(map(int, input().split()))
a.sort()
an = 10 ** 9
for i in range(2 * n):
	for j in range(i + 1, 2 * n):
		if i == j:
			continue
		b = a[:]
		del b[j], b[i]
		c = 0
		for k in range(0, 2 * n - 2, 2):
			c += abs(b[k] - b[k + 1])
		an = min(an, c)
print(an)


n = int(input())
a = sorted([int(f) for f in input().split()])
m = 1 << 31
for x in range(2 * n):
	for y in range(x + 1, 2 * n):
		b = a[:]
		b.pop(x)
		b.pop(y - 1)
		m = min(m, sum([abs(b[x] - b[x + 1]) for x in range(0, len(b), 2)]))
print(m)


import copy

def main():
	n = int(input())
	weights = list(map(int, input().split()))
	mn = 10001
	for i in range(len(weights)):
		for j in range(i + 1, len(weights)):
			tmp = weights.copy()
			tmp.remove(weights[j])
			tmp.remove(weights[i])
			tmp.sort()
			sum = 0
			k = 0
			while k < len(tmp):
				sum += tmp[k + 1] - tmp[k]
				k += 2
			mn = min(sum, mn)
	print(mn)
main()


n = int(input())
people = [int(x) for x in input().split()]
people.sort()
ans = 9999999999
for i in range(n * 2):
	for j in range(n * 2 - 1):
		if i != j:
			counter = 0
			temp_people = people.copy()
			temp_people.pop(i)
			temp_people.pop(j)
			for k in reversed(range(0, n - 1)):
				counter += temp_people[len(temp_people) - 1] - temp_people[len(temp_people) - 2]
				temp_people.pop(len(temp_people) - 1)
				temp_people.pop(len(temp_people) - 1)
			ans = min(counter, ans)
print(ans)


from sys import stdin, stdout
n = int(stdin.readline())
values = sorted(list(map(int, stdin.readline().split())))
ans = float('inf')
for i in range(2 * n):
	for j in range(i + 1, 2 * n):
		res = []
		for z in range(2 * n):
			if z == i or z == j:
				continue
			res.append(values[z])
		cnt = 0
		for q in range(0, len(res), 2):
			cnt += res[q + 1] - res[q]
		ans = min(ans, cnt)
stdout.write(str(ans))


n = int(input())
weights = [int(x) for x in input().split()]
weights = sorted(weights, reverse=True)
s = 0

def lap(weights):
	first = weights[0]
	second = weights[1]
	totalInstability = 0
	for k in range(0, len(weights), 2):
		totalInstability += first - second
		try:
			first = weights[k + 2]
			second = weights[k + 3]
		except:
			s = 0
	return totalInstability
minInstability = lap(weights[2:])
for i in range(2 * n):
	for j in range(i + 1, 2 * n):
		currWeights = weights[0:i] + weights[i + 1:j] + weights[j + 1:]
		currInstability = lap(currWeights)
		if currInstability < minInstability:
			minInstability = currInstability
print(minInstability)


import itertools
n = int(input())
weights = sorted([int(x) for x in input().split(' ')])
combs = itertools.combinations(weights, len(weights) - 2)

def instability(c):
	return sum([abs(c[i + 1] - c[i]) for i in range(0, len(c), 2)])
min_instability = float('inf')
for c in combs:
	min_instability = min(instability(c), min_instability)
print(min_instability)


N = int(input())
w = list(map(int, input().split()))
w.sort()
ans = float('inf')
for i in range(len(w)):
	for j in range(i + 1, len(w)):
		new_w = []
		for k in range(len(w)):
			if k != i and k != j:
				new_w.append(w[k])
		total_instability = 0
		for k in range(0, len(new_w), 2):
			total_instability += new_w[k + 1] - new_w[k]
		ans = min(total_instability, ans)
print(ans)


def main():
	n = int(input())
	n *= 2
	a = list(map(int, input().split()))
	a.sort()
	o = 919478437678234
	for i in range(0, n - 1):
		for j in range(i + 1, n):
			oo = 0
			s = 0
			while s < n - 1:
				if i == s or j == s:
					s += 1
				elif s + 1 == i or s + 1 == j:
					oo += a[s + 2] - a[s]
					s += 3
				else:
					oo += a[s + 1] - a[s]
					s += 2
			o = min(o, oo)
	print(o)
main()


n = int(input()) * 2
lst = [int(i) for i in input().split()]
num = 99999999999999
for i in range(n - 1):
	for i2 in range(i + 1, n):
		sum_ = 0
		nums = []
		for m in range(n):
			if m != i2 and m != i:
				nums.append(lst[m])
		nums = sorted(nums)
		for k in range(0, len(nums), 2):
			sum_ += nums[k + 1] - nums[k]
		num = min(num, sum_)
print(num)


n = int(input())
t = [int(i) for i in input().split()]
t.sort()
ans = []
for i in range(len(t)):
	for j in range(i + 1, len(t)):
		a = t[:i] + t[i + 1:j] + t[j + 1:]
		s = sum(a[1::2]) - sum(a[::2])
		ans.append(s)
print(min(ans))


n = int(input())
a = list(map(int, input().split(' ')))
a.sort()
mini = 100000000000
for i in range(len(a)):
	for j in range(i + 1, len(a)):
		lmin = 0
		x = 0
		y = 1
		while y < len(a):
			if x == i or x == j:
				x += 1
				continue
			if y == i or y == j or y == x:
				y += 1
				continue
			lmin += abs(a[x] - a[y])
			x += 2
			y += 2
		mini = min(lmin, mini)
print(mini)


n = 2 * int(input())
w = sorted(map(int, input().split()))
r = 10000
for i in range(n):
	wi = w.pop(i)
	for j in range(i):
		wj = w.pop(j)
		r = min(r, sum((w[i + 1] - w[i] for i in range(0, n - 3, 2))))
		w.insert(j, wj)
	w.insert(i, wi)
print(r)


n = int(input())
a = [int(x) for x in input().split()]
diffs = []
a.sort()
for i in range(len(a) - 1):
	for j in range(i + 1, len(a)):
		sam = a[:i] + a[i + 1:j] + a[j + 1:]
		diffs.append(sum(sam[1::2]) - sum(sam[::2]))
print(min(diffs))


n = int(input())
arr = list(map(int, input().split()))
arr.sort()
minIns = 0
for k in range(len(arr) - 1):
	minIns += arr[k + 1] - arr[k]
for i in range(0, 2 * n):
	for j in range(i + 1, 2 * n):
		newArr = arr[0:i] + arr[i + 1:j] + arr[j + 1:]
		minIns = min(minIns, sum((newArr[k + 1] - newArr[k] for k in range(0, len(newArr) - 1, 2))))
print(minIns)


n = int(input())
v = [int(i) for i in input().split()]
v = sorted(v)

def dp(i, chose):
	if chose == 0:
		d = 0
		while i < len(v):
			d += v[i + 1] - v[i]
			i += 2
		return d
	if i >= len(v) - 1:
		return 0
	return min(v[i + 1] - v[i] + dp(i + 2, chose), dp(i + 1, chose - 1))
print(dp(0, 2))


y = int(input())
z = list(map(int, input().split()))
z.sort(reverse=True)
difs = []
mini = 1000

def btsheel(lista, ind1, ind2):
	return lista[:ind1] + lista[ind1 + 1:ind2] + lista[ind2 + 1:]
for i in range(2 * y - 1):
	for j in range(i + 1, 2 * y):
		new = btsheel(z, i, j)
		temp = 0
		for k in range(0, 2 * y - 2, 2):
			temp = temp + (new[k] - new[k + 1])
		if temp <= mini:
			mini = temp
print(mini)


n = int(input())
a = sorted(list(map(int, input().split())))
mn = []
b = []
for i in range(len(a)):
	for j in range(i + 1, len(a)):
		b = a[:i] + a[i + 1:j] + a[j + 1:]
		s = sum(b[1::2]) - sum(b[::2])
		mn.append(s)
print(min(mn))


N = 2 * int(input())
W = list(map(int, input().split()))
W.sort()
from itertools import combinations

def it():
	for (i, j) in combinations(range(N), r=2):
		k = 0
		cnt = 0
		w = None
		for k in range(N):
			if not (k == i or k == j):
				if w is None:
					w = W[k]
				else:
					cnt += abs(w - W[k])
					w = None
		yield cnt
print(min(it()))


def strip2(nums, s1, s2):
	res = [0] * (len(nums) - 2)
	j = 0
	for i in range(0, len(nums)):
		if i == s1 or i == s2:
			continue
		res[j] = nums[i]
		j += 1
	return res

def countPairwiseDiff(nums):
	total = 0
	for i in range(1, len(nums), 2):
		total += nums[i] - nums[i - 1]
	return total

def completeSearch(nums):
	nums = sorted(nums)
	ans = 1999999999
	for skip1 in range(len(nums) - 1):
		for skip2 in range(skip1 + 1, len(nums)):
			total = countPairwiseDiff(strip2(nums, skip1, skip2))
			if total < ans:
				ans = total
	print(ans)

def test():
	completeSearch([101, 100, 99, 5, 4, 3, 2, 1])
	completeSearch([1, 3, 4, 6, 3, 4, 100, 200])
	completeSearch([1, 2, 3, 40, 50, 99, 100, 101])
	completeSearch([1, 9, 10, 20, 100, 1000, 1001, 10001])

def nia():
	s = input()
	while len(s) == 0:
		s = input()
	s = s.split()
	iVal = []
	for i in range(len(s)):
		iVal.append(int(s[i]))
	return iVal

def solve():
	n = input()
	completeSearch(nia())
solve()


def foo(ls):
	ls.sort()
	return sum([ls[i + 1] - ls[i] for i in range(0, len(ls) - 1, 2)])
n = int(input())
w = list(map(int, input().split()))
ans = 1005000
for i in range(len(w) - 1):
	for j in range(i + 1, len(w)):
		ans = min(ans, foo([w[l] for l in range(len(w)) if l != i and l != j]))
print(ans)


numPeople = int(input('')) * 2
peopleWeights = input('').split(' ')
peopleWeights = [int(x) for x in peopleWeights]
peopleWeights.sort()
minUns = 9999999999
for i in range(numPeople):
	for j in range(numPeople):
		if i < j:
			curUns = 0
			temp = peopleWeights.copy()
			temp.pop(j)
			temp.pop(i)
			for k in range(numPeople // 2 - 1):
				curUns += temp[2 * k + 1] - temp[2 * k]
			if curUns < minUns:
				minUns = curUns
print(minUns)


n = int(input())
w = list(map(int, input().split()))
w.sort()
p = 2 * n
num = []
for i in range(p):
	for j in range(i + 1, p):
		l = []
		dif = 0
		for k in range(p):
			if k != i and k != j:
				l.append(w[k])
		for x in range(1, n):
			dif += l[2 * x - 1] - l[2 * x - 2]
		num.append(dif)
print(min(num))


n = int(input())
w = list(map(int, input().split()))
w.sort()
ans = []
for i in range(2 * n):
	for j in range(i + 1, 2 * n):
		m = w[0:i] + w[i + 1:j] + w[j + 1:]
		var = sum(m[1::2]) - sum(m[::2])
		ans.append(var)
print(min(ans))


N = int(input())
weight = list(map(int, input().split()))
weight.sort()
mc = -1
for i in range(0, len(weight) - 1):
	for x in range(i + 1, len(weight)):
		count = 0
		tl = weight.copy()
		tl.pop(i)
		tl.pop(x - 1)
		for k in range(0, len(tl) - 1, 2):
			count += tl[k + 1] - tl[k]
		if mc == -1:
			mc = count
		if count < mc:
			mc = count
print(mc)


n = [int(i) for i in input().split()][0]
w = [int(i) for i in input().split()]
ans = 999999
w = sorted(w)
for i0 in range(0, 2 * n):
	for i1 in range(0, i0):
		t = 0
		w0 = 0
		for i in range(0, 2 * n):
			if i == i0 or i == i1:
				continue
			if w0 == 0:
				w0 = w[i]
			else:
				t += w[i] - w0
				w0 = 0
		ans = min(ans, t)
print(ans)


n = int(input())
a = [int(x) for x in input().split()]
a.sort()
ans = []
for i in range(n * 2):
	for j in range(i + 1, n * 2):
		b = a[:i] + a[i + 1:j] + a[j + 1:]
		s = sum(b[1::2]) - sum(b[::2])
		ans.append(s)
print(min(ans))


n = int(input())
v = [int(x) for x in input().split()]
v.sort()
ans = []
for i in range(2 * n):
	for j in range(i + 1, 2 * n):
		B = v[:i] + v[i + 1:j] + v[j + 1:]
		summa = sum(B[1::2]) - sum(B[::2])
		ans.append(summa)
print(min(ans))


import copy
n = 0
w = []

def main():
	get_data()
	get_min_instability()

def get_data():
	global n
	global w
	n = eval(input())
	w = sorted(list(map(int, input().split())))

def get_instability(w):
	total_instability = 0
	for i in range(len(w) // 2):
		total_instability += abs(w[2 * i] - w[2 * i + 1])
	return total_instability

def remove(arr, i, j):
	new_arr = arr
	new_arr[i] = None
	new_arr[j] = None
	while None in new_arr:
		new_arr.remove(None)
	return new_arr

def get_min_instability():
	min_instability = None
	for i in range(len(w)):
		for j in range(len(w)):
			if i == j:
				continue
			instability = get_instability(remove(copy.deepcopy(w), i, j))
			if min_instability == None:
				min_instability = instability
				continue
			min_instability = min(min_instability, instability)
	print(min_instability)
main()


n = int(input().strip().split()[0]) * 2
a = [int(x) for x in input().strip().split()]
a.sort()
ans = 1000000000
for i in range(n):
	for j in range(i + 1, n):
		idx = 0
		res = 0
		for k in range(n // 2 - 1):
			while idx == i or idx == j:
				idx += 1
			r = idx + 1
			while r == i or r == j:
				r += 1
			res = res + a[r] - a[idx]
			idx = r + 1
		ans = min(ans, res)
print(ans)


n = int(input())
A = sorted([int(x) for x in input().split()])
result = sum(A)
for i in range(2 * n):
	for j in range(i + 1, 2 * n):
		B = A[:i] + A[i + 1:j] + A[j + 1:]
		s = 0
		for j in range(n - 1):
			s += B[2 * j + 1] - B[2 * j]
		result = min([result, s])
print(result)


n = int(input())
l = input().split()
for i in range(2 * n):
	l[i] = int(l[i])
l.sort()
m = []
for i in range(2 * n):
	for j in range(i):
		k = l[:]
		k.remove(k[i])
		k.remove(k[j])
		a = []
		for q in range(n - 1):
			a.append(k[2 * q + 1] - k[2 * q])
		a.sort()
		b = 0
		for p in a:
			b += p
		m.append(b)
print(min(m))


N = input()
weights = list(map(int, input().split()))
weights.sort()
minCount = -1
for i in range(0, len(weights) - 1):
	for j in range(i + 1, len(weights)):
		count = 0
		tempWeights = weights.copy()
		del tempWeights[i]
		del tempWeights[j - 1]
		for k in range(0, len(tempWeights) - 1, 2):
			count += tempWeights[k + 1] - tempWeights[k]
		if minCount == -1 or count < minCount:
			minCount = count
print(minCount)


from itertools import combinations
n = int(input())
weights = list(map(int, input().split(' ')))
weights = sorted(weights)
best = float('inf')
for (first, second) in combinations(range(len(weights)), 2):
	result = weights[0:first] + weights[first + 1:second] + weights[second + 1:len(weights)]
	it = iter(result)
	total = 0
	for _ in range(int(len(result) / 2)):
		total += sum([abs(next(it) - next(it))])
	best = min(best, total)
print(best)


n = int(input())
weights = list(map(int, input().split()))
pairs = []
for i in range(2 * n):
	for j in range(2 * n):
		if i != j:
			pairs.append([i, j])
total_diff = 10000000000
for pair in pairs:
	diff = 0
	new_weights = weights.copy()
	new_weights.pop(pair[0])
	new_weights.pop(pair[1] - 1)
	new_weights.sort()
	for i in range(n - 1):
		diff += new_weights[2 * i + 1] - new_weights[2 * i]
	total_diff = min(total_diff, diff)
print(total_diff)


n = int(input())
a = list(map(int, input().split()))
a.sort()
cap = []
res = []
for i in range(0, 2 * n - 1, 2):
	for j in range(i + 1, 2 * n, 2):
		f = 0
		first = 1
		cap = []
		for k in range(2 * n):
			if k == i or k == j:
				continue
			if first:
				f = a[k]
				first = 0
			else:
				first = 1
				cap.append(abs(a[k] - f))
		result = sum(cap)
		res.append(result)
print(min(res))


n = input()
kayaks = list(map(int, input().split(' ')))
kayaks.sort()

def calc_sum(kayaks):
	curr_sum = 0
	for i in range(1, len(kayaks), 2):
		curr_sum += kayaks[i] - kayaks[i - 1]
	return curr_sum
min_sum = sum(kayaks)
for i in range(len(kayaks)):
	for j in range(i + 1, len(kayaks)):
		new_kayaks = kayaks[0:i] + kayaks[i + 1:j] + kayaks[j + 1:]
		min_sum = min(min_sum, calc_sum(new_kayaks))
print(min_sum)


n = int(input())
da = list(map(int, input().split()))
da.sort()
min = 9999999
for a in range(2 * n):
	for b in range(a + 1, 2 * n):
		ans = 0
		p = -1
		for i in range(0, 2 * n):
			if i == a or i == b:
				continue
			if p == -1:
				p = da[i]
			else:
				ans += da[i] - p
				p = -1
		min = min if ans > min else ans
print(min)


n = int(input())
n *= 2
a = [int(i) for i in input().split()]
a.sort()
ans = 100000000
for i in range(n):
	for j in range(i + 1, n):
		b = a[:i] + a[i + 1:j] + a[j + 1:]
		cr = 0
		for k in range(1, len(b), 2):
			cr += b[k] - b[k - 1]
		ans = min(ans, cr)
print(ans)


def main():
	n = int(input())
	wei = []
	num = input().split(' ')
	for i in range(0, 2 * n):
		w = int(num[i])
		wei.append(w)
	weight = sorted(wei)
	result = 100000000000
	for i in range(0, 2 * n):
		for j in range(0, 2 * n):
			inslist = []
			insum = 0
			for k in range(0, 2 * n):
				if k != i and k != j:
					inslist.append(weight[k])
			for k in range(0, 2 * (n - 1), 2):
				insum = insum + inslist[k + 1] - inslist[k]
			result = min(result, insum)
	print(result)
main()


n = int(input())
ws = sorted(list(map(int, input().split(' '))))
res = 10 ** 10

def f(vs):
	return sum((abs(a - b) for (a, b) in zip(vs[0::2], vs[1::2])))
for i in range(len(ws)):
	for j in range(i + 1, len(ws)):
		test = ws[:i] + ws[i + 1:j] + ws[j + 1:]
		res = min(res, f(test))
print(res)


n = int(input())
t = list(map(int, input().split()))
t.sort()
t.append(0)
a = [0] * (n + 1)
b = [0] * (n + 1)
for i in range(n):
	j = 2 * i
	a[i] = a[i - 1] + t[j + 1] - t[j]
	b[i] = b[i - 1] + t[j] - t[j - 1]
s = a[n - 1]
for i in range(0, n):
	for j in range(i, n):
		s = min(s, a[i - 1] + b[j] - b[i] + a[n - 1] - a[j])
print(s)


import math
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
min1 = -1
for i in range(2 * n - 1):
	for j in range(i + 1, 2 * n):
		x = []
		a[i] = -1 * a[i]
		a[j] = -1 * a[j]
		now = a[1]
		prev = a[0]
		i1 = 1
		while i1 < 2 * n:
			if now >= 0 and prev >= 0:
				x.append(abs(now - prev))
				now = a[min(i1 + 2, 2 * n - 1)]
				prev = a[min(i1 + 1, 2 * n - 1)]
				i1 += 2
			if prev < 0:
				prev = now
				now = a[min(i1 + 1, 2 * n - 1)]
				i1 += 1
			if now < 0:
				now = a[min(i1 + 1, 2 * n - 1)]
				i1 += 1
		x.sort()
		sum1 = 0
		for i1 in range(n - 1):
			sum1 += x[i1]
		if min1 == -1:
			min1 = sum1
		a[i] = -1 * a[i]
		a[j] = -1 * a[j]
		min1 = min(min1, sum1)
print(min1)


N = int(input())
ans = 1000000000.0
weights = sorted(map(int, input().split()))
for x in range(2 * N):
	for y in range(x + 1, 2 * N):
		rest = [weights[z] for z in range(2 * N) if z != x and z != y]
		curr = sum((rest[z] - rest[z - 1] for z in range(1, len(rest), 2)))
		ans = min(ans, curr)
print(ans)


n = int(input())
a = [int(z) for z in input().split()]
n = n * 2
out = int(1000000000.0)

def pos(cur, i, j):
	if cur != i and cur != j:
		return cur
	else:
		return pos(cur + 1, i, j)
a.sort()
for i in range(n):
	for j in range(i + 1, n):
		ans = 0
		k = 0
		while True:
			one = pos(k, i, j)
			k = one + 1
			two = pos(k, i, j)
			if two >= n:
				break
			k = two + 1
			ans += abs(a[one] - a[two])
		out = min(out, ans)
print(out)


n = int(input())
n *= 2
a = list(map(int, input().split()))
a.sort()
res = 1 << 62
for i in range(n):
	for j in range(i + 1, n):
		b = a[:i] + a[i + 1:j] + a[j + 1:]
		res = min(res, sum([b[_] - b[_ - 1] for _ in range(1, len(b), 2)]))
print(res)


n = int(input())
a = list(map(int, input().split()))
a.sort()
m = float('inf')
for i in range(0, 2 * n - 1):
	for j in range(i + 1, 2 * n):
		k = 0
		ans = 0
		if j != i + 1:
			while k < 2 * n:
				if k == i or k == j:
					k += 1
				elif k + 1 == i or k + 1 == j:
					b = a[k + 2]
					ans += b - a[k]
					k += 3
				else:
					b = a[k + 1]
					ans += b - a[k]
					k += 2
		if j == i + 1:
			while k < 2 * n:
				if k == i:
					k += 2
				elif k + 1 == i:
					b = a[k + 3]
					ans += b - a[k]
					k += 4
				else:
					b = a[k + 1]
					ans += b - a[k]
					k += 2
		m = min(m, ans)
print(m)


n = int(input())
next_line = input()
arr = next_line.split(' ')
arr = [int(i) for i in arr]
arr.sort()
mintotal = 100001
for y in range(0, 2 * n):
	for z in range(0, 2 * n):
		if y != z:
			newarr = []
			curtotal = 0
			for x in range(0, 2 * n):
				if x != z and x != y:
					newarr.append(arr[x])
			newarr.sort()
			for x in range(1, 2 * n - 2, 2):
				curtotal += newarr[x] - newarr[x - 1]
			mintotal = min(mintotal, curtotal)
print(mintotal)


N = int(input())
N *= 2
W = []
W = input().split()
for i in range(len(W)):
	W[i] = int(W[i])
W.sort()
instab = 1000000000.0
for i in range(0, N):
	for j in range(i + 1, N):
		a = []
		for z in range(N):
			if z != i and z != j:
				a.append(W[z])
		total = 0
		for k in range(0, N - 2, 2):
			total += a[k + 1] - a[k]
		instab = min(instab, total)
print(instab)


n = int(input())
A = list(map(int, input().split()))
import itertools
ans = 10 ** 18
for c in itertools.combinations(range(2 * n), 2):
	(c1, c2) = c
	B = []
	for i in range(2 * n):
		if i != c1 and i != c2:
			B.append(A[i])
	B.sort()
	temp = 0
	for i in range(n - 1):
		temp += B[2 * i + 1] - B[2 * i]
	ans = min(ans, temp)
print(ans)


def main():
	n = 2 * int(input())
	a = list(map(int, input().split()))
	a.sort()
	ans = 10 ** 9 + 7
	for i in range(n):
		for j in range(i + 1, n):
			b = []
			b.extend(a)
			b.remove(a[i])
			b.remove(a[j])
			cnt = 0
			for l in range(1, n - 2, 2):
				cnt += b[l] - b[l - 1]
			ans = min(ans, cnt)
	print(ans)
main()


n = int(input())
x = list(map(int, input().split()))
x.sort()
mn = 10 ** 10
for a in range(2 * n):
	for b in range(a + 1, 2 * n):
		p = x[:a] + x[a + 1:b] + x[b + 1:]
		sm = 0
		for i in range(n - 1):
			sm += p[2 * i + 1] - p[2 * i]
		mn = min(mn, sm)
print(mn)


s = int(input())
n = 2 * s
a = [int(x) for x in input().split()]
a.sort()
m = 10 ** 100
for i in range(n - 1):
	for j in range(i + 1, n):
		b = []
		for k in range(n):
			if k != i and k != j:
				b.append(a[k])
		summa = 0
		for k in range(0, n - 3, 2):
			summa = summa + abs(b[k] - b[k + 1])
		if summa < m:
			m = summa
print(m)


import itertools
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 10000000
for i in range(2 * n):
	for j in range(i + 1, 2 * n):
		x = 0
		b = a + []
		del b[i], b[j - 1]
		for k in range(0, 2 * (n - 1), 2):
			x += abs(b[k] - b[k + 1])
		if x < ans:
			ans = x
print(ans)


from sys import maxsize, stdout, stdin, stderr
mod = int(1000000000.0 + 7)

def I():
	return int(stdin.readline())

def lint():
	return [int(x) for x in stdin.readline().split()]

def S():
	return input().strip()

def grid(r, c):
	return [lint() for i in range(r)]
from collections import defaultdict, Counter
import math
import bisect
from itertools import groupby

def gcd(a, b):
	while b:
		a %= b
		tmp = a
		a = b
		b = tmp
	return a

def lcm(a, b):
	return a / gcd(a, b) * b

def check_prime(n):
	for i in range(2, n):
		if n % i == 0:
			return 0
	return 1

def Bs(a, x):
	i = 0
	j = 0
	left = 0
	right = len(a)
	flag = False
	while left < right:
		mi = (left + right) // 2
		if a[mi] <= x:
			left = mi + 1
			i += 1
		else:
			right = mi
			j += 1
	if left > 0 and a[left - 1] == x:
		return (i - 1, j)
	else:
		return (-1, -1)
n = I()
s = lint()
s.sort()
ans = 1000000000
for i in range(2 * n):
	for j in range(i + 1, 2 * n):
		d = []
		for k in range(2 * n):
			if k != i and k != j:
				d.append(s[k])
		tmp = 0
		for t in range(0, len(d), 2):
			tmp += d[t + 1] - d[t]
		ans = min(ans, tmp)
print(ans)


n = int(input())
w = input()
weights = [int(x) for x in w.split(' ')]
weights.sort()

def get_instability(i, j):
	test = weights[:min(i, j)] + weights[min(i, j) + 1:max(i, j)] + weights[max(i, j) + 1:]
	instability = 0
	for k in range(0, len(test) - 1, 2):
		instability += abs(test[k] - test[k + 1])
	return instability
instabilities = []
for i in range(len(weights)):
	for j in range(len(weights)):
		if i == j:
			continue
		instabilities.append(get_instability(i, j))
print(min(instabilities))


def solution(x):
	x.sort()
	min_ans = x[-1] - x[0]
	for L in range(len(x) - 1):
		for R in range(L + 1, len(x)):
			cur_ans = 0
			indexes = list(range(L)) + list(range(L + 1, R)) + list(range(R + 1, len(x)))
			for k in range(1, len(indexes), 2):
				cur_ans += x[indexes[k]] - x[indexes[k - 1]]
			if cur_ans < min_ans:
				min_ans = cur_ans
	return min_ans
N = int(input())
x = list(map(int, input().split()))
print(solution(x))


n = int(input())
w = sorted(map(int, input().split()))
ans = 1e+100
for i in range(2 * n):
	for j in range(i + 1, 2 * n):
		prev = -1
		s = 0
		for k in range(2 * n):
			if k == i or k == j:
				continue
			if prev == -1:
				prev = w[k]
			else:
				s += w[k] - prev
				prev = -1
		ans = min(ans, s)
print(ans)


n = int(input())
w = list(map(int, input().split()))
w.sort()
m = 10 ** 20
for i in range(2 * n):
	for j in range(i + 1, 2 * n):
		v = []
		s = 0
		for k in range(2 * n):
			if k != i and k != j:
				v.append(w[k])
		for k in range(0, len(v) - 1, 2):
			s += v[k + 1] - v[k]
		if s < m:
			m = s
print(m)


def solve(n, ar):
	ar = sorted(ar)
	n = 2 * n
	cnt = 0
	temp = []
	ans = 999999999
	for i in range(n - 1):
		for j in range(i + 1, n):
			for k in range(n):
				if k == i or k == j:
					continue
				temp.append(ar[k])
			for z in range(0, len(temp), 2):
				cnt += abs(temp[z] - temp[z + 1])
			temp = []
			ans = min(ans, cnt)
			cnt = 0
	print(ans)
n = int(input())
ar = list(map(int, input().split()))
solve(n, ar)


from collections import Counter
import string
import bisect
import math
import sys
from fractions import Fraction

def array_int():
	return [int(i) for i in sys.stdin.readline().split()]

def vary(arrber_of_variables):
	if arrber_of_variables == 1:
		return int(sys.stdin.readline())
	if arrber_of_variables >= 2:
		return map(int, sys.stdin.readline().split())

def makedict(var):
	return dict(Counter(var))
testcases = 1
for _ in range(testcases):
	n = vary(1)
	num = array_int()
	num.sort()
	mini = math.inf
	for i in range(2 * n):
		for j in range(i + 1, 2 * n):
			numt = num[:]
			numt.pop(i)
			numt.pop(j - 1)
			ans = 0
			for k in range(0, 2 * n - 2, 2):
				ans += numt[k + 1] - numt[k]
			mini = min(ans, mini)
	print(mini)


n = int(input())
list = [int(x) for x in input().split(' ')]
l = sorted(list)
result = max(list)
for i in range(len(l)):
	for j in range(len(l)):
		l = sorted(list)
		if i == j:
			break
		else:
			l[i] = 0
			l[j] = 0
		l.remove(0)
		l.remove(0)
		temp = 0
		k = 0
		while k < len(l):
			term = l[k + 1] - l[k]
			temp += term
			k += 2
		result = min(result, temp)
print(result)


n = int(input())
lst = []
for x in input().split():
	lst.append(int(x))
lst.sort()
k = 50000
for x in range(len(lst) - 1):
	for y in range(x + 1, len(lst)):
		acc = 0
		a = lst[:x] + lst[x + 1:y] + lst[y + 1:]
		for z in range(0, len(a) - 1, 2):
			acc += a[z + 1] - a[z]
		k = min(k, acc)
print(k)


n = int(input())
v = [int(i) for i in input().split()]
count = 0
m = float('inf')
for i in range(len(v)):
	for j in range(i + 1, len(v)):
		c = []
		for k in range(len(v)):
			if k == i or k == j:
				continue
			c.append(v[k])
		c.sort()
		p = 0
		for k in range(0, len(c), 2):
			p += c[k + 1] - c[k]
		if p < m:
			m = p
print(m)


n = int(input())
w = list(map(int, input().split()))
ans = 10 ** 6
w.sort()
for i in range(n * 2):
	for j in range(i + 1, n * 2):
		t = w[:i] + w[i + 1:j] + w[j + 1:]
		temp = 0
		for k in range(n - 1):
			temp += t[k * 2 + 1] - t[k * 2]
		ans = min(ans, temp)
print(ans)


n = int(input())
L = sorted(list(map(int, input().split())))
v = lambda x: sum((x[i] - x[i - 1] for (i, _) in enumerate(x) if i % 2 == 1))
m = 100000
for p in range(2 * n):
	for q in range(p + 1, 2 * n):
		LL = L[:]
		del LL[p]
		del LL[q - 1]
		m = min(m, v(LL))
print(m)


n = int(input())
a = list(map(int, input().split()))
res = int(1000000000.0 + 7)
for i in range(2 * n):
	for j in range(i + 1, 2 * n):
		b = [a[k] for k in range(2 * n) if k != i and k != j]
		b.sort()
		s = 0
		for k in range(n - 1):
			s += b[2 * k + 1] - b[2 * k]
		res = min(res, s)
print(res)


def readinput():
	data = sys.stdin.read().strip().split('\n')
	n = int(data[0])
	p = sorted([int(i) for i in data[1].split()])
	return (2 * n, p)

def main():
	(n, p) = readinput()
	instability = set()
	for i in range(n):
		for j in range(i + 1, n):
			instability.add(solve(i, j, p, n))
	print(min(instability))

def solve(i, j, p, n):
	idx1 = 0
	count = 0
	while True:
		while idx1 == i or idx1 == j:
			idx1 += 1
		if idx1 >= n:
			break
		idx2 = idx1 + 1
		while idx2 == i or idx2 == j:
			idx2 += 1
		count += abs(p[idx1] - p[idx2])
		idx1 = idx2 + 1
	return count
import sys
main()


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
a = list(map(int, input().split()))
n *= 2
a.sort()
r = 1000000
for i in range(n - 1):
	for j in range(i + 1, n):
		curr = 0
		s = list(a[:i] + a[i + 1:j] + a[j + 1:])
		for k in range(1, len(s), 2):
			curr += s[k] - s[k - 1]
		r = min(r, curr)
print(r)


n = int(input())
w = [int(c) for c in input().split()]
w.sort()
res = []
for i in range(n * 2):
	for j in range(i + 1, n * 2):
		r = w[:i] + w[i + 1:j] + w[j + 1:]
		res.append(sum(r[1::2]) - sum(r[0::2]))
print(min(res))


n = int(input())
line = list(map(int, input().split()))
line.sort()
ans = 10000000000
for i in range(n * 2 - 1):
	for j in range(i + 1, n * 2):
		ans1 = 0
		prev = 0
		for k in range(n * 2):
			if k == i or k == j:
				continue
			if prev == 0:
				prev = line[k]
			else:
				ans1 += line[k] - prev
				prev = 0
		ans = min(ans, ans1)
print(ans)


from sys import stdin, stdout

def func(data, x, y):
	data_c = data[:]
	data_c.remove(x)
	data_c.remove(y)
	result = 0
	for x in range(len(data_c) // 2):
		result += abs(data_c[x * 2] - data_c[x * 2 + 1])
	return result
n = int(stdin.readline().rstrip())
data = list(map(int, stdin.readline().rstrip().split()))
data.sort()
mnx = sum(data)
for x in range(n * 2):
	for y in range(n * 2):
		if x != y:
			mnx = min(mnx, func(data, data[x], data[y]))
stdout.write(str(mnx))


n = int(input())
w = list(map(int, input().split(' ')))
w.sort()
min = 1000000
for i in range(2 * n - 1):
	for j in range(i + 1, 2 * n):
		sum = 0
		sch = 0
		h = 0
		while h < 2 * n - 1 and sch != 2 * n - 2:
			sch += 2
			if h != i and h != j:
				if h + 1 != i and h + 1 != j:
					sum += abs(w[h] - w[h + 1])
					h += 2
				else:
					sum += abs(w[h] - w[h + 2])
					h += 3
			elif h + 1 != i and h + 1 != j:
				sum += abs(w[h + 1] - w[h + 2])
				h += 3
			else:
				sum += abs(w[h + 2] - w[h + 3])
				h += 4
		if sum < min:
			min = sum
print(min)


n = int(input())
w = list(map(int, input().split(' ')))
w.sort()
best = sum(w)
for i in range(0, 2 * n):
	for j in range(i + 1, 2 * n):
		k = 0
		k2 = 1
		s = 0
		while k2 < 2 * n:
			while k == i or k == j:
				k += 1
			if k >= 2 * n:
				break
			k2 = k + 1
			while k2 == i or k2 == j:
				k2 += 1
			s += w[k2] - w[k]
			k = k2 + 1
			k2 = k + 1
		if s < best:
			best = s
print(best)


n = int(input())
arr = input().split()
for i in range(2 * n):
	arr[i] = int(arr[i])
arr.sort()
b = [0] * (n * 2)
ctr = 0
best = 1000000
for i in range(2 * n):
	for j in range(i + 1, 2 * n):
		for k in range(2 * n):
			b[k] = arr[k]
		b[i] = -1
		b[j] = -1
		b.sort()
		ctr = 0
		for k in range(2, 2 * n - 1, 2):
			ctr += b[k + 1] - b[k]
		best = min(best, ctr)
print(best)