Призрак Джа играет с резиновыми утятами. У него есть $$$n$$$ кучек резиновых утят, расставленных в ряд, где $$$i$$$-я кучка содержит $$$a_i$$$ утят. Утёнок Кряк даёт Призраку Джа строго возрастающую последовательность $$$b_1,b_2,\ldots,b_n$$$ и приказывает ему сделать так, чтобы кучки $$$a_1,a_2,\ldots,a_n$$$ стали ровно этой последовательностью.
Процесс, который выполняет Джа, состоит из следующих двух этапов:
Формально, для каждой кучки $$$i$$$ он выбирает целое неотрицательное число $$$x_i$$$ и заменяет $$$a_i$$$ на $$$a_i+x_i$$$.
Формально, он может выполнять следующую операцию любое количество раз, возможно ноль: выбрать индекс $$$i$$$ такой, что $$$1\le i\le n-1$$$, и поменять местами значения $$$a_i$$$ и $$$a_{i+1}$$$.
Процесс называется допустимым, если после завершения обоих этапов последовательность размеров кучек равна ровно $$$b_1,b_2,\ldots,b_n$$$.
Найдите минимально возможное количество операций, выполненных на втором этапе, среди всех допустимых процессов. Если допустимого процесса не существует, выведите $$$-1$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 2000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1\le n\le 2000$$$) — количество кучек резиновых утят.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$) — начальное количество резиновых утят в каждой кучке.
Третья строка содержит $$$n$$$ целых чисел $$$b_1,b_2,\ldots,b_n$$$ ($$$1\le b_1 \lt b_2 \lt \cdots \lt b_n\le 10^9$$$) — конечное количество резиновых утят в каждой кучке.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2000$$$.
Для каждого набора входных данных выведите единственное целое число — минимально возможное количество операций, выполненных на втором этапе, среди всех допустимых процессов. Если допустимого процесса не существует, выведите $$$-1$$$.
1031 2 21 3 532 2 11 2 325 12 466 5 4 3 2 11 2 3 4 5 674 7 1 6 2 5 31 2 3 4 5 6 722 12 343 2 2 11 2 3 444 3 2 11 3 4 551 5 4 3 22 3 4 5 6510 3 8 6 93 6 8 9 10
02-1151204435
В первом наборе входных данных Джа нужен только первый этап. Он может выбрать $$$x_1=0,x_2=1,x_3=3$$$, тогда кучки становятся $$$1,3,5$$$. Обмены не нужны, поэтому ответ равен $$$0$$$.
Во втором наборе входных данных Джа нужны оба этапа. Он может выбрать $$$x_1=0,x_2=1,x_3=0$$$, тогда кучки становятся $$$2,3,1$$$. Затем он может выполнить два обмена: $$$$$$ [2,3,1]\to [2,1,3]\to [1,2,3]. $$$$$$ Кучка с $$$1$$$ утёнком должна переместиться с третьей позиции на первую, поэтому необходимо не менее двух обменов. Следовательно, ответ равен $$$2$$$.
В третьем наборе входных данных это невозможно. Первая кучка изначально содержит $$$5$$$ утят, но каждое число в целевой последовательности не превышает $$$4$$$. Поскольку Джа может только добавлять утят и не может их убирать, эта кучка не может стать равной ни одному числу в целевой последовательности. Следовательно, ответ равен $$$-1$$$.
В четвёртом наборе входных данных утят добавлять не нужно. Джа нужно лишь переставить кучки в порядке возрастания. Минимальное количество соседних обменов равно $$$15$$$.
В пятом наборе входных данных утят добавлять не нужно. Снова Джа нужно лишь переставить кучки в порядке возрастания. Минимальное количество соседних обменов равно $$$12$$$.
