Вам заданы два массива длины \(n\): \(a_1, a_2, \dots, a_n\) и \(b_1, b_2, \dots, b_n\).
Вы можете применить к ним следующую операцию произвольное количество раз:
- Выбрать позицию \(i\) (\(1 \le i \le n\));
- Поменять местами \(a_i\) и \(b_i\).
Чему равна наименьшая возможная сумма \(|a_1 - a_2| + |a_2 - a_3| + \dots + |a_{n-1} - a_n|\) \(+\) \(|b_1 - b_2| + |b_2 - b_3| + \dots + |b_{n-1} - b_n|\) (другими словами, \(\sum\limits_{i=1}^{n - 1}{\left(|a_i - a_{i+1}| + |b_i - b_{i+1}|\right)}\)), которую можно получить после применения заданной операции произвольное количество раз (возможно, ни разу)?
Выходные данные
Для каждого набора входных данных выведите одно целое число — наименьшую возможную сумму \(\sum\limits_{i=1}^{n-1}{\left(|a_i - a_{i+1}| + |b_i - b_{i+1}|\right)}\).
Примечание
В первом наборе входных данных мы можем, например, поменять местами \(a_3\) с \(b_3\) и \(a_4\) с \(b_4\). Мы получим массивы \(a = [3, 3, 3, 3]\) и \(b = [10, 10, 10, 10]\) с суммой \(3 \cdot |3 - 3| + 3 \cdot |10 - 10| = 0\).
Во втором наборе массивы уже имеют наименьшую сумму (описанную ранее), равную \(|1 - 2| + \dots + |4 - 5| + |6 - 7| + \dots + |9 - 10|\) \(= 4 + 4 = 8\).
В третьем наборе мы можем, например, поменять местами \(a_5\) с \(b_5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
3 3 10 10
10 10 3 3
5
1 2 3 4 5
6 7 8 9 10
6
72 101 108 108 111 44
10 87 111 114 108 100
|
0
8
218
|