You are given 2 arrays $a$ and $b$, both of size $n$. You can swap two elements in $b$ at most once (or leave it as it is), and you are required to minimize the value $$\sum_{i}|a_{i}-b_{i}|.$$

Find the minimum possible value of this sum.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le {10^9}$).

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le {10^9}$).


-----Output-----

Output the minimum value of $\sum_{i}|a_{i}-b_{i}|$.


-----Examples-----

Input
5
5 4 3 2 1
1 2 3 4 5
Output
4
Input
2
1 3
4 2
Output
2


-----Note-----

In the first example, we can swap the first and fifth element in array $b$, so that it becomes $[ 5, 2, 3, 4, 1 ]$.

Therefore, the minimum possible value of this sum would be $|5-5| + |4-2| + |3-3| + |2-4| + |1-1| = 4$.

In the second example, we can swap the first and second elements. So, our answer would be $2$.

Difficulty: VERY_HARD
Tags: Complete search

Sorting

Data structures

Constructive algorithms
Skill types: Sorting

Data structures

Complete search

Starter code:

Solutions:
n = int(input())
lis = []
a = list(map(int, input().split()))
b = list(map(int, input().split()))
allsum = sum([abs(a[i] - b[i]) for i in range(n)])
ans = 0
lis = []
for i in range(n):
	if a[i] < b[i]:
		lis.append((a[i], 1, b[i]))
	elif a[i] > b[i]:
		lis.append((b[i], 2, a[i]))
lis.sort()
nmax = 0
for (x, ty, y) in lis:
	if ty == 1:
		nmax = max(nmax, y)
	else:
		ans = max(ans, min(y - x, nmax - x))
lis = []
for i in range(n):
	if a[i] > b[i]:
		lis.append((b[i], 1, a[i]))
	elif a[i] < b[i]:
		lis.append((a[i], 2, b[i]))
lis.sort()
nmax = 0
for (x, ty, y) in lis:
	if ty == 1:
		nmax = max(nmax, y)
	else:
		ans = max(ans, min(y - x, nmax - x))
print(allsum - ans * 2)


n = int(input())
a = [int(val) for val in input().split()]
b = [int(val) for val in input().split()]
s = []
t = []
for i in range(n):
	if a[i] < b[i]:
		s.append((a[i], b[i]))
	elif a[i] > b[i]:
		t.append((b[i], a[i]))
s.sort()
t.sort()
x = []
y = []
for i in range(len(s)):
	if i > 0 and s[i][1] < s[i - 1][1]:
		continue
	x.append(s[i])
for i in range(len(t)):
	if i > 0 and t[i][1] < t[i - 1][1]:
		continue
	y.append(t[i])

def get_overlap(t1, t2):
	x_max = max(t1[0], t2[0])
	y_min = min(t1[1], t2[1])
	return max(y_min - x_max, 0)
j = 0
max_overlap = 0
for i in range(len(x)):
	while j < len(y) and y[j][1] < x[i][1]:
		overlap = get_overlap(x[i], y[j])
		if overlap > max_overlap:
			max_overlap = overlap
		j += 1
	if j < len(y):
		overlap = get_overlap(x[i], y[j])
		if overlap > max_overlap:
			max_overlap = overlap
dist = 0
for i in range(n):
	dist += abs(a[i] - b[i])
dist -= 2 * max_overlap
print(dist)


n = int(input())
a = [int(val) for val in input().split()]
b = [int(val) for val in input().split()]

def get_overlap(x, y):
	return max(min(x[1], y[1]) - max(x[0], y[0]), 0)
x = []
y = []
for i in range(n):
	if a[i] < b[i]:
		x.append((a[i], b[i]))
	elif a[i] > b[i]:
		y.append((b[i], a[i]))
max_overlap = 0
if len(x) > 0 and len(y) > 0:
	x.sort()
	y.sort()
	x2 = []
	y2 = []
	for i in range(len(x)):
		if i > 0 and x[i][1] <= x[i - 1][1]:
			continue
		x2.append(x[i])
	for i in range(len(y)):
		if i > 0 and y[i][1] <= y[i - 1][1]:
			continue
		y2.append(y[i])
	j = 0
	k = 0
	for i in range(len(x2)):
		while k < len(y2) and y2[k][1] <= x2[i][1]:
			overlap = get_overlap(x2[i], y2[k])
			if overlap > max_overlap:
				max_overlap = overlap
			k += 1
		else:
			if k < len(y2):
				overlap = get_overlap(x2[i], y2[k])
				if overlap > max_overlap:
					max_overlap = overlap
dist = 0
for i in range(n):
	dist += abs(a[i] - b[i])
dist -= 2 * max_overlap
print(dist)


MAX = 10 ** 9 + 10
n = int(input())
A = [int(t) for t in input().split()]
B = [int(t) for t in input().split()]
S = sorted(set(A) | set(B) | {0})
order = {x: i for (i, x) in enumerate(S)}
N = len(S)

class SegTree:

	def __init__(self):
		self.arr = [0] * 2 * N

	def update(self, i, v):
		i += N
		while i:
			self.arr[i] = max(self.arr[i], v)
			i //= 2

	def query(self, l, r):
		l += N
		r += N
		res = 0
		while l < r:
			if l & 1:
				res = max(self.arr[l], res)
				l += 1
			if r & 1:
				r -= 1
				res = max(res, self.arr[r])
			l //= 2
			r //= 2
		return res
down_len = SegTree()
down_b = SegTree()
up_len = SegTree()
up_a = SegTree()
tot = 0
best = 0
P = sorted((p for p in zip(A, B)), key=lambda p: max(p))
for (a, b) in P:
	(ai, bi) = (order[a], order[b])
	if a < b:
		_1 = up_a.query(0, ai) - a
		_2 = up_len.query(ai, bi)
		cur = min(max(_1, _2), b - a)
		best = max(best, cur)
		down_b.update(ai, b)
		down_len.update(ai, b - a)
	elif b < a:
		_1 = down_b.query(0, bi) - b
		_2 = down_len.query(bi, ai)
		cur = min(max(_1, _2), a - b)
		best = max(best, cur)
		up_a.update(bi, a)
		up_len.update(bi, a - b)
	tot += abs(a - b)
print(tot - 2 * best)


import sys
from sys import stdin
n = int(stdin.readline())
lis = []
a = list(map(int, stdin.readline().split()))
b = list(map(int, stdin.readline().split()))
allsum = 0
for i in range(n):
	allsum += abs(a[i] - b[i])
ans = 0
lis = []
for i in range(n):
	if a[i] < b[i]:
		lis.append((a[i], 1, b[i]))
	elif a[i] > b[i]:
		lis.append((b[i], 2, a[i]))
lis.sort()
nmax = 0
for (x, ty, y) in lis:
	if ty == 1:
		nmax = max(nmax, y)
	else:
		ans = max(ans, min(y - x, nmax - x))
lis = []
for i in range(n):
	if a[i] > b[i]:
		lis.append((b[i], 1, a[i]))
	elif a[i] < b[i]:
		lis.append((a[i], 2, b[i]))
lis.sort()
nmax = 0
for (x, ty, y) in lis:
	if ty == 1:
		nmax = max(nmax, y)
	else:
		ans = max(ans, min(y - x, nmax - x))
print(allsum - ans * 2)