Дана последовательность из \(n\) целых чисел \(a_1, a_2, \dots, a_n\). Также даны \(x\) целых чисел \(1, 2, \dots, x\).
Вас просят вставить каждое из этих дополнительных целых чисел в последовательность \(a\). Каждое число можно вставлять в начало последовательности, в конец последовательности или между любыми элементами последовательности.
Счет полученной последовательности \(a'\) равен сумме абсолютных разностей соседних элементов в ней \(\left(\sum \limits_{i=1}^{n+x-1} |a'_i - a'_{i+1}|\right)\).
Какой наименьший счет может быть у последовательности \(a'\)?
Выходные данные
На каждый набор входных данных выведите одно целое число — наименьшую сумму абсолютных разностей соседних элементов в последовательности после того, как вы вставите в нее дополнительные числа.
Примечание
Здесь представлены последовательности с наименьшим счетом в примере. Подчеркнутые элементы — это дополнительные числа. Обратите внимание, что существуют и другие последовательности с наименьшим счетом.
- \(\underline{1}, \underline{2}, \underline{3}, \underline{4}, \underline{5}, 10\)
- \(\underline{7}, 7, \underline{6}, \underline{4}, 2, \underline{2}, \underline{1}, \underline{3}, \underline{5}, \underline{8}, 10\)
- \(6, \underline{1}, 1, \underline{2}, 5, 7, 3, 3, 9, 10, 10, 1\)
- \(1, 3, \underline{1}, 1, 2, \underline{2}, \underline{3}, \underline{4}, \underline{5}, \underline{6}, \underline{7}, \underline{8}, \underline{9}, \underline{10}\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 5
10
3 8
7 2 10
10 2
6 1 5 7 3 3 9 10 10 1
4 10
1 3 1 2
|
9
15
31
13
|