Вам даны два массива \(a\) и \(b\) длины \(n\). Массив \(a\) содержит все нечетные целые числа от \(1\) до \(2n\) в некотором порядке, а массив \(b\) содержит все четные целые числа от \(1\) до \(2n\) в некотором порядке.
Вы можете выполнять следующую операцию с этими массивами:
- выбрать один из двух массивов;
- выбрать индекс \(i\) от \(1\) до \(n-1\);
- поменять местами \(i\)-й и \((i+1)\)-й элементы выбранного массива.
Вычислите минимальное количество операций, необходимое для того, чтобы сделать массив
\(a\) лексикографически меньше массива
\(b\).
Если массивы \(x\) и \(y\) одинаковой длины \(n\) различны, то мы говорим, что \(x\) лексикографически меньше \(y\), если в первой позиции, где \(x\) и \(y\) различны, в последовательности \(x\) элемент меньше, чем соответствующий элемент в \(y\).
Выходные данные
Для каждого набора входных данных выведите одно целое число: минимальное количество операций, необходимое, чтобы сделать массив \(a\) лексикографически меньше массива \(b\).
Можно показать, что ответ всегда существует.
Примечание
В первом примере массив \(a\) уже лексикографически меньше массива \(b\), поэтому не нужно делать никаких операций.
Во втором примере можно поменять местами \(5\) и \(3\), а затем поменять местами \(2\) и \(4\), тогда массивы будут равны \([3, 5, 1]\) и \([4, 2, 6]\). Другое возможное решение — поменять местами \(3\) и \(1\), а затем поменять местами \(5\) и \(1\), тогда массивы будут равны \([1, 5, 3]\) и \([2, 4, 6]\). Еще одно решение — поменять местами \(4\) и \(6\), а затем — \(2\) и \(6\), тогда массивы будут равны \([5, 3, 1]\) и \([6, 2, 4]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
3 1
4 2
3
5 3 1
2 4 6
5
7 5 9 1 3
2 4 6 10 8
|
0
2
3
|